Authors Aram W. Harrow, Alexandra Kolla, Leonard J. Schulman,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 10 (3), 2014, pp. 55–75
www.theoryofcomputing.org
S PECIAL ISSUE : A NALYSIS OF B OOLEAN F UNCTIONS
Dimension-Free L2 Maximal Inequality for
Spherical Means in the Hypercube
Aram W. Harrow∗ Alexandra Kolla† Leonard J. Schulman‡
Received February 21, 2013; Revised November 12, 2013; Published May 23, 2014
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.
ACM Classification: G.3
AMS Classification: 42B25
Key words and phrases: maximal inequality, Fourier analysis, boolean hypercube
1 Introduction
Let In be the n-dimensional hypercube: the set {0, 1}n equipped with Hamming metric
d(x, y) = |{i : xi 6= yi }| .
n
Let V = RI be the vector space of real-valued functions on the hypercube. For x ∈ In , let πx denote the
evaluation map1 from V → R defined by πx f = f (x), for f ∈ V . If A ⊆ Hom(V,V ) (the vector space
∗ 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.
† Was at Microsoft Research at the beginning and during part of this work.
‡ 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.
1 This notation choice is because our paper is replete with operators acting on functions, and the associative composition
πx A f is preferable to the cumbersome (A f )(x).
© 2014 Aram W. Harrow, Alexandra Kolla, and Leonard J. Schulman
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2014.v010a003
A RAM W. H ARROW, A LEXANDRA KOLLA , AND L EONARD J. S CHULMAN
consisting of all linear mappings from V into itself), the maximal operator MA : V → V is the sublinear
operator in which MA f is defined by
πx MA f = sup πx A f . (1.1)
A∈A
Of interest is the family S = {Sk }nk=0 of spherical means, the stochastic linear operators Sk : V → V
given by
1
πx Sk f = n ∑ πy f .
k {y:d(x,y)=k}
Applying M, we have the spherical maximal operator MS : V → V defined by
πx MS f = max πx Sk f . (1.2)
0≤k≤n
The result of this paper is the following dimension-free bound.
Theorem 1.1. There is a constant AI such that for all n, kMS k2→2 < AI .
Equivalently, for all n and f , kMS f k2 ≤ AI k f k2 .
Maximal inequalities for various function spaces such as L p (Rn ), and with stochastic linear operators
defined by various distributions such as uniform on spheres (as above), uniform on balls, or according to
the distribution of a random walk of specified length (ergodic averaging), have been extensively studied;
see [27] for a good review. Most previous work does not explicitly consider finite or discrete metric
spaces; however, see [28] for a maximal inequality on the free group on finitely many generators.
One may ask whether the hypercube bound should follow from known results for larger spaces.
The hypercube of dimension greater than 1 does not embed isometrically in Euclidean space of any
dimension [10, 25], so inequalities for Euclidean spaces do not seem to be a useful starting point. The
hypercube does embed isometrically in Rn with the L1 norm, but there is no maximal inequality for
this metric. To see this, still in the context of discrete metric spaces, consider the space Z2 with the L1
distance. Fixing any nonnegative integer N let f be the indicator function of
x : ∑ xi = 0, ∑ |xi | ≤ 2N .
Then k f k22 = 2N + 1 while kMS f k22 ∈ Ω(N 2 ). A similar gap (between O(N n−1 ) and Ω(N n )) occurs in
any fixed dimension n, because there exists a set of size O(N n−1 ) constituting a positive fraction of Ω(N n )
L1 -spheres, necessarily of many radii. It is therefore not the L1 metric structure of the hypercube which
makes a maximal inequality possible, but, essentially, its bounded side-length.
1.1 Combinatorial interpretation
In the special case that f is the indicator function of a set of vertices F in In , Theorem 1.1 has the
following consequence: For nonnegative ε less than some ε0 and for all n, if |F| <√ε2n then there exists
x ∈ In such that in every sphere about x, the fraction of points which lie in F is O( ε).
The aspect of interest is that this holds for every sphere about x. The analogous claim for a fixed
radius is a trivial application of the Markov inequality; by a union bound the same holds for any constant
number of radii. Avoiding the union bound over all n + 1 radii is the essence of the maximal inequality.
T HEORY OF C OMPUTING, Volume 10 (3), 2014, pp. 55–75 56
D IMENSION -F REE L2 M AXIMAL I NEQUALITY FOR S PHERICAL M EANS IN THE H YPERCUBE
The combinatorial interpretation also has an edge version. Let F 0 be a set of edges in In . Let the
distance from a point to an edge be the distance to the closer point on that edge. Theorem 1.1 has the
following consequence: For nonnegative ε less than some ε1 and for all n, if |F 0 | < √ εn2n then there exists
x ∈ In such that in every sphere about x, the fraction of edges which lie in F 0 is O( ε). (Define √a function
f on vertices by f (y) = the fraction of edges adjacent to y that lie in F 0 . Note that k f k2 ∈ O( ε). Apply
Theorem 1.1 to f . For the desired conclusion observe that in the sphere of edges of distance k from x, the
fraction of edges lying in F 0 is bounded for k ≤ n/2 by 2πx Sk f , and for k > n/2 by 2πx Sk+1 f .)
1.2 Maximal inequalities and Unique Games on the hypercube
In this section we discuss one of the motivations for the present work, although our main result does not
directly yield progress on the question.
Khot’s Unique Games Conjecture (UGC) [14] has, for a decade, been the focus of great attention.
Either resolution of the conjecture will have implications for the hardness of approximating NP-hard
problems. Falsification, in particular, is likely to provide powerful new algorithmic techniques. On
the other hand verification of UGC will imply that improving the currently best known approximation
algorithms for many important computational problems such as M IN -2S AT-D ELETION [14], V ERTEX
C OVER [16], M AXIMUM C UT [15] and non-uniform S PARSEST C UT [6, 17], is NP-hard. In addition,
in recent years, UGC has also proved to be intimately connected to the limitations of semidefinite
programming (SDP). Making this connection precise, the authors of [4] and [29] show that if UGC is true,
then for every constraint satisfaction problem (CSP) the best approximation ratio is given by a certain
simple SDP. While the UGC question, in short, is arguably among the most important challenges in
computational complexity, the current evidence in either direction is not strong, and there is no consensus
regarding the likely answer.
A Unique Game instance is specified by an undirected constraint graph G = (V, E), an integer k
which is the alphabet size, a set of variables {xu }u∈V , one for each vertex u, and a set of permutations
(constraints) πuv : [k] → [k], one for each (u, v) s.t. {u, v} ∈ E, with πuv = (πvu )−1 . An assignment of
values in [k] to the variables is said to satisfy the constraint on the edge {u, v} if πuv (xu ) = xv . The
optimization problem is to assign a value in [k] to each variable xu so as to maximize the number of
satisfied constraints.
Khot [14] conjectured that it is NP-hard to distinguish between the cases when almost all, or very
few, of the constraints of a Unique Game are satisfiable:
Conjecture 1.2 (UGC). For any constants ε, δ > 0, there is a k(ε, δ ) such that for any k > k(ε, δ ), it
is NP-hard to distinguish between instances of Unique Games with alphabet size k where at least 1 − ε
fraction of constraints are satisfiable and those where at most δ fraction of constraints are satisfiable.
Numerous works have focused on designing approximation algorithms for Unique Games. While
earlier papers [14, 32, 13, 5, 7] presented efficient algorithms for any instance that might have very poor
approximation guarantees when run on the worst case input, recent works have focused on ruling out
hardness for large classes of instances. Such instances include expanders [3, 26], local expanders [2, 30],
and more generally, graphs with a few large eigenvalues [19]. In [20], hardness of random and semi-
random distributions over instances is also ruled out. We note that in [1], a sub-exponential time algorithm
for general instances is given.
T HEORY OF C OMPUTING, Volume 10 (3), 2014, pp. 55–75 57
A RAM W. H ARROW, A LEXANDRA KOLLA , AND L EONARD J. S CHULMAN
This recent line of work can be seen as a strategy to disprove UGC by ruling out hardness of instances
largely based on their spectral profile, and more specifically the number of “large enough" eigenvalues
(small set expansion) of the instance’s constraint graph. Following this strategy, the question to ask next
is what type of graphs are the ones on which all those techniques fail. The hypercube is typical of such
graphs, with its spectrum lying in a “temperate zone" in terms of expansion. This property, along with the
high symmetry of the hypercube, makes it a natural next frontier toward disproving UGC.
It is typical when dealing with a 1−ε satisfiable instance to think of it as originating from a completely
satisfiable instance, where a malicious adversary picks an ε fraction of edges in the constraint graph
and “spoils” them, by modifying their corresponding constraints. Some likely algorithms for Unique
Games on the hypercube are seed-and-propagate (exhaustively range over assignments for a small subset
of nodes and propagate the assignment from those nodes according to the constraints on the edges, using
some fixed conflict resolution strategy), or “local SDP.” In either case the performance of these algorithms
depends on whether the adversary can “rip up” the graph enough so that the algorithm has difficulty
propagating the seeded values, or otherwise combining local solutions into larger regions—even though
in a pure expansion sense the graph is not so easy to rip up that the algorithm could afford to work just in
local patches of the graph and throw away all the edges between patches. A good strategy to show that
the adversary can win is to show that the adversary can select an ε fraction of the edges of the graph in
such a way that around every seed vertex x there is a sphere in which a majority of the of the edges have
been selected by the adversary.
Theorem 1.1 shows that, to the contrary, no adversary has this power.
It is a challenging problem to analyze the performance of seed-and-propagate algorithms, but the
maximal inequality is a favorable indication for the research program aimed at showing their effectiveness.
Regarding seed-and-propagate on the hypercube we only add that seeding at a single vertex is
insufficient, as the graph is sufficiently weakly connected that a sub-linear number of edge removals
suffices to partition it into components each of sub-linear size. However multiple seedings remains a very
viable strategy.
1.3 Possible generalizations
Let G = (V, E) be any finite connected graph, with shortest-path metric dG . Let Gn be the nth Cartesian
power of G, the graph on V n in which (v, w) is an edge if there is a unique i for which (vi , wi ) ∈ E. The
shortest path metric on Gn is therefore the L1 metric induced by dG . Spherical operators and spherical
maximal operators are now defined, and we conjecture that Theorem 1.1 holds for a suitable constant AG .
Our proof techniques would require modification even for the next simplest cases of G taken to be the
path or the complete graph on three vertices.
In a different direction, the existence of a dimension-free bound for all In invites the question whether
there is a natural limit object T , such that for every In there exists a single morphism In → T and thus
each n occurs in it as a special case.
1.4 Proof overview
Our proof is in two main steps, in each of which we obtain a maximal inequality for one class of operators
based on comparison with another more tractable class. To introduce the first of these reductions we
T HEORY OF C OMPUTING, Volume 10 (3), 2014, pp. 55–75 58
D IMENSION -F REE L2 M AXIMAL I NEQUALITY FOR S PHERICAL M EANS IN THE H YPERCUBE
need to define the senate operator2 Sen. Let T = {Tk } be any family of operators indexed by a parameter
k which varies over an interval [0, a] (a possibly infinite) of either nonnegative reals or nonnegative
integers. (E. g., S = {Sk }n0 as above.) Then the family Sen(T) = {Sen(T)k }, indexed by k in the same
range, consists of the operators
1 k
Z k
1
Sen(T)k = ∑ T` or Sen(T)k = T` d`
k + 1 `=0 k 0
depending as k ranges over integers or reals, and taking the limit from above at k = 0 in the continuous
case.
In the first step of our argument we follow a comparison method due to Stein [31] to show that
Proposition 1.3. kMS k2→2 ∈ O(1 + kMSen(S) k2→2 ).
Bounds on the Krawtchouk polynomials play a key role in this argument. We will introduce the
polynomials and prove these bounds in Section 2, and then use them to prove Proposition 1.3 in Section 3.
To introduce the second reduction we need to define the family of stochastic noise operators N =
{Nt }t≥0 indexed by real t. Letting p = (1 − e−t )/2, we set
n
n k
Nt = ∑ p (1 − p)n−k Sk .
k=0 k
This has the following interpretation. πx Nt f is the expectation of πy f where y is obtained by running n
independent Poisson processes with parameter 1 from time 0 to time t, and re-randomizing the ith bit of x
as many times as there are events in the ith Poisson process. The Nt form a semigroup: Nt1 Nt2 = Nt1 +t2 .
The process is equivalent to a Poisson-clocked random walk on the hypercube.
We show (in Section 4) by a direct pointwise comparison that:
Proposition 1.4. kMSen(S) k2→2 ∈ O(kMSen(N) k2→2 ).
√
Finally (see [23]) kMSen(N) k2→2 ≤ 2 2 (indeed, kMSen(N) k p→p ≤ (p/(p − 1))1/p for p > 1) by
previous results: the Hopf-Kakutani-Yosida maximal inequality and Marcinkiewicz’s interpolation
theorem. For the reader’s convenience, we restate these results in the Appendix.
Combining these results, we have Theorem 1.1 by
kMS f k2 ∈ O(k f k2 + kMSen(S) f k2 ) ⊆ O(k f k2 + kMSen(N) f k2 ) ⊆ O(k f k2 ) .
Remark 1.5. While our main result is in terms of the 2 → 2 norm, many of our techniques generalize to
other norms. Here we are limited by Proposition 1.3, which does not conveniently generalize to other
norms. Very recently, this difficulty has been overcome by Krause; for a preliminary version of his work
see [22]. On the other hand, kMS k1→1 = n + 1, as can be seen by taking f to be nonzero only on a single
point.
We are concerned in this paper solely with maximal operators for sets A of nonnegative matrices. For
any such maximal operator MA , |πx MA f | ≤ πx MA | f |. So it suffices to show Theorem 1.1 for nonnegative
f ; this simplifies some expressions and will be assumed throughout.
2 The terminology is to express that (as in the United States Senate) each block has equal weight without regard to size.
T HEORY OF C OMPUTING, Volume 10 (3), 2014, pp. 55–75 59
A RAM W. H ARROW, A LEXANDRA KOLLA , AND L EONARD J. S CHULMAN
2 Fourier analysis and Krawtchouk polynomials
n √
For y ∈ In , define the character χy ∈ RI by πx χy = (−1)x·y / 2n . The normalization is chosen so that the
n
χy form an orthonormal basis of RI . This basis simultaneously diagonalizes each Sk , as they commute
with In as an abelian group. A direct calculation (see also [11]) shows that
(n)
Sk χy = κk (|y|)χy , (2.1)
(n)
where |y| = |{i : yi = 1}|, and κk (|y|) is the normalized kth Krawtchouk polynomial, defined by
x n−x
k
(n) j k− j
κk (x) = ∑ (−1) j n
. (2.2)
j=0 k
We collect here some facts about Krawtchouk polynomials.
Lemma 2.1.
(n) (n)
1. k-x Symmetry: κk (x) = κx (k).
(n) (n)
2. Reflection symmetry: κk (n − x) = (−1)k κk (x).
3. Orthogonality:
n
2n
(n) (n) n
∑ κk (x)κ` (x) = n δk,` . (2.3)
x=0 x k
(n) p
4. Roots: The roots of κk (x) are real, distinct, and lie in the range n/2 ± k(n − k).
The proofs of the first three claims are straightforward (see [24]), and the fourth claim is a weaker
(n)
version of Theorem 8 of [21]. We sometimes abbreviate κk (x) = κk (x).
Before going into further technical detail, we give an overview of our goals in this section. As we have
noted in Section 1, maximal inequalities are easily proved for semigroups, such as the noise poperators
Nt . In some ways Sk resembles Nk/n , since Nt is approximately an average of Sk for k = nt ± nt(1 − t).
While direct comparison is difficult (e. g., writing Sk as a linear combination of Nt necessarily entails
large coefficients), we can argue that the spectra of these operators should be qualitatively similar.
Indeed, the Nt are also diagonal in the χy basis, and for |y| = x, their eigenvalue for χy is (1 − 2t)x .
Thus, our goal in this section will be to show that κk (x) has similar behavior3 to (1 − 2k/n)x . More
precisely, we prove
Lemma 2.2. There is a constant c > 0 such that for all n and integer 0 ≤ x, k ≤ n/2,
(n)
|κk (x)| ≤ e−ckx/n . (2.4)
Due to Lemma 2.1.1,2 it suffices to bound κk (x) only when 0 ≤ k ≤ x ≤ n/2.
3 This qualitative similarity breaks down when k (or x) is close to n/2, although this case will not be the main contribution to
our bounds. See the introduction to [18] for discussion of the properties of the Sn/2 operator.
T HEORY OF C OMPUTING, Volume 10 (3), 2014, pp. 55–75 60
D IMENSION -F REE L2 M AXIMAL I NEQUALITY FOR S PHERICAL M EANS IN THE H YPERCUBE
Proof. The main complication in working with Krawtchouk polynomials is that they have several different
forms of asymptotic behavior depending on whether x and k are in the lower, middle or upper part of
their range; indeed, [9] breaks the asymptotic properties of κk (x) into 12 different cases. However, for
our purpose, we need only two different upper bounds on the Krawtchouk polynomials, based on whether
k/n is greater than or less than 0.14; a somewhat arbitrary threshold that we will see the justification for
below.
Case I: k, x ≥ 0.14n. This is the simpler upper bound, which relies only on the orthogonality property
Lemma 2.1.3. Setting k = ` in Lemma 2.1.3 and observing that all of the terms on the LHS are nonnegative,
it follows that
2n
κk2 (x) ≤ n n . (2.5)
k x
Based on Stirling’s formula, Lemma 17.5.1 of [8] states that
enH2 (p) enH2 (p)
n
≥p ≥ √ (2.6)
np 8p(1 − p)n 2n
where H2 (p) := −p ln p − (1 − p) ln(1 − p).
Note that H2 (0.14) > ln(2)/2, so, for k, x ≥ 0.14n, (2.5) implies that
κk2 (x) ≤ 2ne(ln(2)−2H2 (0.14))n ≤ 2ne−c1 n
for some c1 > 0.116. Now let n0 be sufficiently large (n0 = 100 suffices) that c1 ≥ 2 ln(2n0 )/n0 ; then for
all n ≥ n0 , 2ne−c1 n ≤ e−c1 n/2 . So for all n ≥ n0 and all 0.14n ≤ k, x ≤ n/2,
κk2 (x) ≤ e−2c1 (n/2)(n/2)/n ≤ e−2c1 kx/n .
To handle the n < n0 case, we define
n o
(n)
c2 = min −(n/kx) ln |κk (x)| : 1 ≤ k ≤ x ≤ n/2, n < n0 .
(n)
It is immediate from Definition (2.2) that |κk (x)| < 1 if 1 ≤ k, x ≤ n − 1, so c2 > 0.
Finally, the lemma follows with c = min{2c1 , c2 }.
Case II: k ≤ 0.14n or x ≤ 0.14n. By the symmetry between k and x, we can assume without loss of
generality that k ≤ 0.14n.
It is convenient to make the change of variable
x = (1 − z)n/2 ,
set
µk (z) = κk ((1 − z)n/2) ,
and expand µk as µk (z) = ∑ki=0 αk,i zi . µk is either symmetric or anti-symmetric about 0, and we focus on
bounding |µk | in the range 0 ≤ z ≤ 1 corresponding to 0 ≤ x ≤ n/2.
T HEORY OF C OMPUTING, Volume 10 (3), 2014, pp. 55–75 61
A RAM W. H ARROW, A LEXANDRA KOLLA , AND L EONARD J. S CHULMAN
Let y1 , . . . , yk be the roots of µk . By Lemma 2.1.2 the multiset {y1 , . . . , yk } is identical to the multiset
{−y1 , . . . , −yk }. So we can write
k
µk2 (z) = αk,k
2
∏(z2 − y2i ) . (2.7)
i=1
It is immediate from Definition (2.2) that
µk2 (1) = 1 . (2.8)
Furthermore, by Lemma 2.1.4,
2p
ymax := max yi ≤ k(n − k) . (2.9)
i n
We now obtain an upper bound on µk2 (z) simply by maximizing (2.7) subject to the constraints (2.8)
and (2.9). Observe that
µ 2 (z) k 2
z − y2i
µk2 (z) = k2 =∏ .
µk (1) i=1 1 − y2i
Consider the problem of choosing yi to maximize a single term |z2 − y2i |/(1 − y2i ). Observe that
∂ z2 − y2i z2 − 1
2 2
= ≤ 0. (2.10)
∂ yi 1 − yi (1 − y2i )2
As a result, the maximum over |yi | < z is found at yi = 0 and the maximum over |yi | > z is found at
yi = ymax . In the former case, |z2 − y2i |/(1 − y2i ) = z2 . In the latter case,
|z2 − y2i | y2max − z2 y2max
≤ ≤ ≤ 0.93 .
1 − y2i 1 − y2max 1 − y2max
√
The last inequality uses the fact that ymax ≤ 2 0.14 · 0.86 (recalling that k ≤ 0.14n). So |z2 − y2i |/(1 −
y2i ) ≤ max(z2 , 0.93), implying that
µk2 (z) ≤ (max(z2 , 0.93))k . (2.11)
If z2 ≥ 0.93 then we use z = 1 − 2x/n ≤ e−2x/n to obtain κk2 (x) ≤ e−4xk/n .
If z2 ≤ 0.93 then (recalling x ≤ n/2) we have
κk2 (x) ≤ (0.93)k ≤ (0.93)2xk/n = e−cxk/n
for c = −2 ln(0.93).
p
The threshold of 0.14 used here could be replaced by any p satisfying H2 (p) > 1/2 > p(1 − p).
T HEORY OF C OMPUTING, Volume 10 (3), 2014, pp. 55–75 62
D IMENSION -F REE L2 M AXIMAL I NEQUALITY FOR S PHERICAL M EANS IN THE H YPERCUBE
3 Senates dominate dictatorships: Proof of Proposition 1.3
Proposition 1.3 (restatement). kMS k2→2 ∈ O(1 + kMSen(S) k2→2 ).
bn/2c
We start by defining S = {Sk }0 . The operator MS : V → V is then defined by
πx MS f = max πx Sk f .
0≤k≤bn/2c
n
Define ι := Sn to be the antipodal operator on RI , i. e., the involution obtained by flipping
√ all n bits
of the argument of the function. Then πx MS f = max{πx MS f , πx ιMS f }. So kMS k2→2 ≤ 2kMS k2→2 .
Proposition 1.3 therefore follows from:
Claim 3.1. There is a C < ∞ such that for all n and f , kMS f k2 ≤ Ck f k2 + kMSen(S) f k2 .
We prove the claim in the following two subsections.
3.1 A method of Stein
The bounds on kS` k2→2 for even and odd radius ` are technically distinct (but not in any interesting way).
We present the arguments in parallel.
3.1.1 Even radius: S2r for 0 ≤ r ≤ rmax = bbn/2c/2c
Note that for n = 4m + a, 0 ≤ a ≤ 3, this gives rmax = m.
Abel’s lemma gives the following easily verified identity:
1 r 1 r
S2r − ∑ S 2k = ∑ k(S2k − S2(k−1) ) . (3.1)
r + 1 k=0 r + 1 k=1
Hence we have the following pointwise (that is to say, valid at each point x) inequality for 0 ≤ r ≤ rmax ,
rmax = bbn/2c/2c:
" #2 " √ #2
1 r k √
r
πx (S2r − ∑ S2k ) f = ∑ · k[πx (S2k − S2(k−1) ) f ]
r + 1 k=0 k=1 r + 1
r r
k
≤∑ 2 ∑ k[πx (S2k − S2(k−1) ) f ]2
k=1 (r + 1) k=1
r
r
= ∑ k[πx (S2k − S2(k−1) ) f ]2
2(r + 1) k=1
1 rmax
≤ ∑ k[πx (S2k − S2(k−1) ) f ]2 .
2 k=1
T HEORY OF C OMPUTING, Volume 10 (3), 2014, pp. 55–75 63
A RAM W. H ARROW, A LEXANDRA KOLLA , AND L EONARD J. S CHULMAN
The first inequality is by Cauchy-Schwarz. This suggests defining an “error term” operator R0 : V → V by
s
1 rmax
πx R0 f = ∑ k[πx (S2k − S2(k−1) ) f ]2
2 k=1
(3.2)
so that for any r ≤ rmax ,
k(S2r − Sen(S)2r ) f k22 ≤ kR0 f k22 . (3.3)
3.1.2 Odd radius: S2r+1 for 0 ≤ r ≤ rmax = b(bn/2c − 1)/2c
Note that for n = 4m + a, 0 ≤ a ≤ 3, this gives
(
m − 1 if a ∈ {0, 1},
rmax =
m if a ∈ {2, 3}.
Abel’s lemma gives:
1 r 1 r
S2r+1 − ∑ 2k+1 r + 1 ∑ k(S2k+1 − S2k−1 ) .
S = (3.4)
r + 1 k=0 k=1
Hence we have the following pointwise inequality for 0 ≤ r ≤ rmax = b(bn/2c − 1)/2c:
" ! #2
1 r
πx S2r+1 − ∑ S2k+1 f =
r + 1 k=0
" √ #2
r
k √
∑ · k[πx (S2k+1 − S2k−1 ) f ]
k=1 r + 1
1 rmax
... ≤ ∑ k[πx (S2k+1 − S2k−1 ) f ]2 .
2 k=1
This suggests defining an “error term” operator R1 : V → V by
s
1 rmax
πx R1 f = ∑ k[πx (S2k+1 − S2k−1 ) f ]2
2 k=1
(3.5)
so that for any r ≤ rmax ,
k(S2r+1 − Sen(S)2r+1 ) f k22 ≤ kR1 f k22 . (3.6)
T HEORY OF C OMPUTING, Volume 10 (3), 2014, pp. 55–75 64
D IMENSION -F REE L2 M AXIMAL I NEQUALITY FOR S PHERICAL M EANS IN THE H YPERCUBE
3.2 Bounding the error term
Define R f by πx R f := max{πx R0 f , πx R1 f }. Combining (3.3) and (3.6) we have for each x ∈ In , each
n
f ∈ RI and each r ≤ n/2,
|πx (Sr − Sen(S)r ) f | ≤ πx R f .
Maximizing the LHS over r, squaring and summing over x, we obtain that
kMS f − MSen(S) f k2 ≤ kR f k2 .
Claim 3.1 (and Proposition 1.3) now follow from the following lemma.
Lemma 3.2. There is a C < ∞ such that kR0 f k2 , kR1 f k2 ≤ Ck f k2 .
Proof. As seen in the preliminaries, the operators Sk commute and share the eigenvectors {χy }y∈In ,
(n)
with eigenvalues given by equation (2.1): Sk χy = κk (|y|)χy . Let Ex be the projection operator on the
n
n (n)
|y| -dimensional eigenspace spanned by {χy }|y|=x ; so Sk = ∑x=0 κk (x)Ex . We calculate:
1 rmax
kR0 f k22 = ∑ 2 ∑ k[((S2k − S2(k−1) ) f )(z)]2
z∈In k=1
rmax n 2
1 (n) (n)
= ∑ k ∑ (κ2k (x) − κ2(k−1) (x))Ex f
2 k=1 2
x=0
rmax
1 n (n) (n)
= ∑ kEx f k22 ∑ k(κ2k (x) − κ2(k−1) (x))2 .
2 x=0 k=1
Likewise: (here and below the value of rmax depends on whether R0 or R1 is being bounded)
1 rmax
kR1 f k22 = ∑n 2 ∑ k[((S2k+1 − S2k−1 ) f )(z)]2
z∈I k=1
rmax
1 n (n) (n)
= ∑ kEx f k22 ∑ k(κ2k+1 (x) − κ2k−1 (x))2 .
2 x=0 k=1
Since k f k22 = ∑nx=0 kEx f k22 , it suffices to show that there is a C < ∞ such that for every 0 ≤ x ≤ n,
" #
rmax 2
(n) (n)
∑ k κ2k (x) − κ2(k−1) (x) ≤ C , (3.7a)
k=1
" #
rmax
(n) (n) 2
∑ k κ2k+1 (x) − κ2k−1 (x) ≤ C . (3.7b)
k=1
Recall that it suffices by Lemma 2.1.2 to consider x ≤ n/2. For x = 0, (3.7) is trivial as the LHS is 0. For
x > 0 we use Lemma 2.1.1 to rewrite the parenthesized term (with ` = 2k or ` = 2k + 1) as follows:
n−1
(n) (n) x−1 (n−1) 2x (n−1)
κx (`) − κx (` − 1) = −2 n κx−1 (` − 1) = − κx−1 (` − 1) .
x
n
T HEORY OF C OMPUTING, Volume 10 (3), 2014, pp. 55–75 65
A RAM W. H ARROW, A LEXANDRA KOLLA , AND L EONARD J. S CHULMAN
(n)
To see this, recall that nx κx (`) counts x-subsets of {1, . . . , n} according to the parity of their intersection
with {1, . . . , `}; now condition on whether the x-subset contains the element `.
Consequently,
(n) (n) 2x (n−1) (n−1)
κx (`) − κx (` − 2) = − κx−1 (` − 1) + κx−1 (` − 2)
n
which by a similar argument is
n−2
4x x−1 (n−2) 4x (n − x) (n−2)
=− κx−1 (` − 2) = − κ (` − 2) . (3.8)
n−1
n x−1 n (n − 1) x−1
The two terms on the LHS of (3.7) are now
rmax 2
(n) (n)
∑ k κx (2k) − κx (2k − 2) (3.9)
k=1
rmax 2 rmax
4x(n − x) (n−2) (n) (n)
2
= ∑k κx−1 (2k − 2) ∑ k κx (2k + 1) − κx (2k − 1)
k=1 n(n − 1) k=1
rmax 2
4x(n − x) (n−2)
= ∑k κ (2k − 1) . (3.10)
k=1 n(n − 1) x−1
For x = 1, quantities (3.10) come to ∑rk=1
max
16kn−2 which is upper bounded by a constant.
For x > 1 we upper bound (3.10), first by
16x2 rmax (n−2) 2 16x2 rmax (n−2) 2
∑ k κ x−1 (2k − 2) and ∑ k κx−1 (2k − 1)
n2 k=1 n2 k=1
which in turn are upper bounded by (applying each value of rmax ):
16x2 bn/2c
(n−2)
2
∑ (k/2 + 1) κx−1 (k) .
n2 k=0
Now apply Lemma 2.2 to upper bound this by
16x2 ∞ −2c(x−1)k/(n−2) 16x2 ∞
∑
n2 k=0
(k/2 + 1)e = ∑ (k/2 + 1)e−αk
n2 k=0
(3.11)
x2 16(1 − e−α ) + 8e−α
= (3.12)
n2 (1 − e−α )2
2
x
≤ 24
n(1 − e−α )
x 2
≤ 24
nα
(n − 2)x 2
= 24
2cn(x − 1)
≤ 24/c2 ,
T HEORY OF C OMPUTING, Volume 10 (3), 2014, pp. 55–75 66
D IMENSION -F REE L2 M AXIMAL I NEQUALITY FOR S PHERICAL M EANS IN THE H YPERCUBE
where in (3.11) we have defined α = 2c(x − 1)/(n − 2) and in (3.12) we have used the identity
∞
∑ ke−αk = e−α (1 − e−α )−2 .
k=0
This completes the requirement of equation (3.7).
4 Comparing senate maximal functions: Proof of Proposition 1.4
Proposition 1.4 (restatement). kMSen(S) k2→2 ∈ O(kMSen(N) k2→2 ).
Proof. The proof relies on pointwise comparison of maximal functions.
If A, B are matrices, write A ≤ B if B − A is a nonnegative matrix. If A, B are sets of nonnegative
matrices indexed by integers or reals, we write A . B if for every A ∈ A there is a probability measure
µA on B such that A ≤ B dµA (B). Observe that in this case for any nonnegative function f and any x,
R
supA∈A πx A f ≤ supB∈B πx B f , and therefore for any norm, kMA k ≤ kMB k (and in particular for k · k2→2 ).
For any k > bn/2c,
πx Sen(S)k f ≤ πx Sen(S)bn/2c ( f + ι f ) .
Therefore kMSen(S) k2→2 ≤ 2kMSen(S) k2→2 . However, we will not compare Sen(S) and Sen(N) directly.
Instead, we will introduce a variant of N that more closely resembles S, but is no longer a semigroup.
Recall that Nt represents the average over independently flipping each bit with probability p =
(1 − e−t )/2. Define Ñp to represent the same noise process but parameterized by p instead of t. Thus
Nt = Ñ 1−e−t and Ñp = N− ln(1−2p) .
2
While the sets {Nt }t≥0 and {Ñp } p∈[0,1/2) are of course the same, their Senate operators Sen(N) and
Sen(Ñ) are different:
1 T
Z
Sen(N)T = Nt dt , (4.1)
T 0
1 P 1 − ln(1−2P) −t
Z Z
Sen(Ñ)P = Ñp dp = e Nt dt . (4.2)
P 0 2P 0
In (4.2), P is varies over (0, 1/2) and in (4.1), T can be any positive real number.
Hence Proposition 1.4 is established in two subsidiary claims:
Lemma 4.1. Sen(Ñ) . Sen(N).
Lemma 4.2. Sen(S) . C · Sen(Ñ) for some constant C > 0.
T HEORY OF C OMPUTING, Volume 10 (3), 2014, pp. 55–75 67
A RAM W. H ARROW, A LEXANDRA KOLLA , AND L EONARD J. S CHULMAN
Proof of Lemma 4.1. For each P we will write Sen(Ñ)P as a convex combination of Sen(N)T for different
values of T . By considering the action of each side on the constant function we will see that it suffices to
write Sen(Ñ)P as a bounded nonnegative combination of Sen(N)T for different values of T (i. e., a linear
combination with coefficients that are nonnegative and whose sum is bounded).
Let f (t) := e−t /2P and τ := − ln(1 − 2P) so that (4.2) becomes
Z τ
Sen(Ñ)P = dt f (t)Nt (4.3)
0
Z τ Z τ
= dt( f (t) − f (τ))Nt
dt f (τ)Nt + (4.4)
0 0
Z τ Z τ
0
= τ f (τ) Sen(N)τ + dt dT (− f (T )) Nt (4.5)
0 t
Z τ Z T
= τ f (τ) Sen(N)τ + dT dt(− f 0 (T ))Nt (4.6)
0 0
Z τ
= τ f (τ) Sen(N)τ + dT (−T f 0 (T )) Sen(N)T . (4.7)
0
Since f 0 (T ) < 0, (4.7) is the desired nonnegative combination. We have written the proof in this way
to stress that the only features of (4.1) and (4.2) used are that Sen(N)T is a “flat” distribution over Nt and
Sen(Ñ)P has Nt weighted by a weakly decreasing function.
Proof of Lemma 4.2. To compare Sen(S̄) and Sen(Ñ), we need to show that for any K ≤ n/2, we can
find a distribution over P such that Sen(S̄)K is pointwise ≤ the appropriate average over Sen(Ñ)P times
a constant. In fact, it will suffice to consider a distribution that is concentrated on a single value of P.
Define √ !
K+ K 1
PK := min , .
n 2
In Lemma 4.3, we will show that Sen(S)K ≤ C · Sen(Ñ)PK , thus implying that Sen(S̄) . C · Sen(Ñ). The
idea behind Lemma 4.3 is that for each k ≤ K, there
√ are significant contributions to√the Sk coefficient
Ä)PK for p throughout the range [k/n, (k + k)/n]. This window has width k/n, contributes
of Sen(
Ω(1/ k) weight to Sk at each point and is normalized by 1/PK ≈ n/K. The total contribution is thus
Ω(1/K).
√
Lemma 4.3. Let n ≥ 9, K ≤ n/2 and PK = min K+n K , 12 . Then Sen(S)K ≤ 3e20 · Sen(Ñ)PK ,
The true constant is certainly much better, and perhaps closer to 1/2. We remark that n ≥ 9 can be
assumed without loss of generality, since kMS k2→2 ≤ n + 1 by the triangle inequality.
Proof. Observe that P := PK ≤ 2K/n.
For 0 ≤ k ≤ K, we now compare the coefficient of Sk in Sen(S)K (where it is 1/(K + 1)) to its value
in Sen(Ñ)P , where it is
1 P
Z
dp B(n, p, k) .
P 0
Denote this latter quantity by ak .
T HEORY OF C OMPUTING, Volume 10 (3), 2014, pp. 55–75 68
D IMENSION -F REE L2 M AXIMAL I NEQUALITY FOR S PHERICAL M EANS IN THE H YPERCUBE
Consider first k = 0. If K = 0 and P = 0, then S0 has weight 1 in both cases. Otherwise P ≥ 1/n, and
1 1/n 1 n
n 1 1
Z
n
a0 ≥ (1 − p) dp ≥ · · 1− ≥ .
P 0 2K n n 8K
This last inequality uses√the fact that (1 − 1/n)n is√
increasing with n and thus is ≥ 1/4 for n ≥ 2.
Next, suppose k + k ≤ n/2. √ Then P ≥ (k + k)/n. We will consider only the contribution to ak
resulting from 0 ≤ p − k/n ≤ k/n. First, use Stirling’s formula to bound
r
n n 1
≥ exp(nH2 (k/n)) ≥ exp(nH2 (k/n)) √ ,
k 9k(n − k) 3 k
implying that
1
B n, n/k, k ≥ √ . (4.8)
3 k
Next, observe that
d k − nq
ln B(n, q, k) = . (4.9)
dq q(1 − q)
√
When k/n ≤ q ≤ p ≤ (k + k)/n, we have
√
k k k
k − nq ≥ k − np ≥ − k and q(1 − q) ≥ 1− ≥ .
n n 2n
√
Thus, 0 ≤ p − k/n ≤ k/n implies that
Z p
B(n, p, k) k − nq
ln = dq (4.10a)
B(n, k/n, k) k/n q(1 − q)
k k − np
≥ p− (4.10b)
n k/2n
≥ −2 . (4.10c)
√ √
Combining (4.8) and (4.10), we find that B(n, p, k) ≥ 1/6e2 k for k/n ≤ p ≤ (k + k)/n. Thus
√ √
1 (k+ k)/n n k 1 1
Z
ak ≥ dp B(n, p, k) ≥ · · √ ≥ .
P k/n 2K n 6e2 k 12e2 K
√
Finally, we consider
p the case when k + k ≥ n/2. In this regime, we have P = 1/2. Also, k ≤ n/2,
so K ≥ k ≥ n/2 − n/2 ≥ n/4 (assuming in the last step that n ≥ 8).
√ √
Consider p ∈ [1/2 − 1/ n, 1/2]. Assume that n ≥ 9 so that 1/2 − 1/ n ≥ 1/6. We can then use
(4.9) to bound
B(n, 21 − √1n , k) √
1 k − n2 + n
k 1
ln ≥− − +√ 1 1
B(n, k/n, k) n 2 n 6·2
2
1
≥ −12 1 − √ ≥ −20 .
2
T HEORY OF C OMPUTING, Volume 10 (3), 2014, pp. 55–75 69
A RAM W. H ARROW, A LEXANDRA KOLLA , AND L EONARD J. S CHULMAN
Similarly
B(n, 1/2, k) 1 k k − n/2
ln ≥ − ≥ −6 .
B(n, k/n, k) 2 n 1/12
We conclude that
Z 1
1 2 1 1 1
ak ≥ dp B(n, p, k) ≥ 2 · √ · √ ≥ 20 .
P 1 √1
2− n
n 3e20 k 3e K
This completes the proof of Lemma 4.2.
A Maximal inequalities on semigroups
In this appendix, we review the maximal ergodic inequality that we use to show kMSen(N) k1→1,w ≤ 1.
Theorem A.1 (maximal ergodic inequality). Let A be a positive sublinear operator with kAk1→1 ≤ 1
and kAk∞→∞ ≤ 1. Let A denote the (discrete) semigroup generated by A. Then
kMSen(A) k1→1,w ≤ 1 .
This inequality was originally proved by Kakutani and Yosida (in the case when A is linear) and Hopf
(for general semigroups). However since the proof of [12] is simple and self-contained, we restate it here.
Proof. For f an arbitrary function and T a nonnegative integer, define E Tf = I[MSen(A)≤T f ≥ 0]. We will
first prove that
hE Tf , f i ≥ 0 , (A.1)
for all T . To see that the theorem follows from this claim, apply (A.1) to f − λ and we find that
λ kE Tf−λ k1 ≤ hE Tf−λ , f i ≤ k f k1 . Thus kE Tf−λ k1 ≤ λ −1 k f k1 . Since this inequality holds for all T , it
implies that kI[MSen(A) f ≥ λ ]k1 is also ≤ λ −1 k f k1 .
We now return to the proof of (A.1). We define for this purpose an unweighted Senate operator:
T
Sen(A)T = ∑ At .
t=0
We abbreviate MT := MSen(A)≤T and M̄T := MSen(A)≤T . Observe that I[MT f ≥ 0] = I[M̄T f ≥ 0]. Also
define, for any function g, the function (g)+ to be the nonnegative part of g.
Thus, if 0 ≤ t ≤ T , then we have Sen(A)t f ≤ M̄T f ≤ (M̄T f )+ . This implies that
f + A(M̄T f )+ ≥ f + ASen(A)t f = Sen(A)t+1 f .
Thus, f ≥ Sen(A)t f − A((M̄T f )+ ), (including an t = 0 case that can be checked separately) and maxi-
mizing over 0 ≤ t ≤ T , we have
f ≥ M̄T f − A((M̄T f )+ ) .
T HEORY OF C OMPUTING, Volume 10 (3), 2014, pp. 55–75 70
D IMENSION -F REE L2 M AXIMAL I NEQUALITY FOR S PHERICAL M EANS IN THE H YPERCUBE
Now we take the inner product of both sides with E Tf and find
hE Tf , f i ≥ hE Tf , M̄T f − A((M̄T f )+ )i (A.2)
= hE Tf , (M̄T f )+ − A((M̄T f )+ )i (A.3)
= k(M̄T f )+ k1 − hE Tf , A((M̄T f )+ )i (A.4)
≥ k(M̄T f )+ k1 − kA((M̄T f )+ )k1 (A.5)
≥ 0. (A.6)
The final inequality uses the fact that kAk1→1 ≤ 1.
For our purposes, we will want to convert the bound on the 1 → 1, w norm into a bound on p → p
norms, especially for p = 2. This is achieved by the Marcinkiewicz interpolation theorem [33].
Theorem A.2. Let A be a sublinear operator with kAk p→p,w ≤ Np and kAkq→q,w ≤ Nq . Then for any
1 ≤ p < r < q ≤ ∞, we have
1/r
δ 1−δ r(q − p)
kAkr→r ≤ 2Np Nq ,
(r − p)(q − r)
with δ = p(q − r)/r(q − p).
In our case, a maximal operator MA has kMA k∞→∞,w = 1 and if A is a positive contractive semigroup,
then Theorem A.1 implies that kMA k1→1,w ≤ 1 as well. This implies that for any 1 < p, we have
1/p
p
kMA k p→p ≤ 2 , (A.7)
p−1
√
which is 2 2 when p = 2.
Acknowledgments
Thanks to Gil Kalai for a stimulating conversation which pointed us in the direction of maximal inequali-
ties, to Konstantin Makarychev and Yury Makarychev for discussions about UGC on the hypercube, and
to Yuval Peres and Terence Tao for helpful comments.
References
[1] S ANJEEV A RORA , B OAZ BARAK , AND DAVID S TEURER: Subexponential algorithms for Unique
Games and related problems. In Proc. 51st FOCS, pp. 563–572. IEEE Comp. Soc. Press, 2010.
[doi:10.1109/FOCS.2010.59] 57
[2] S ANJEEV A RORA , RUSSELL I MPAGLIAZZO , W ILLIAM M ATTHEWS , AND DAVID S TEURER:
Improved algorithms for Unique Games via divide and conquer. Electron. Colloq. on Comput.
Complexity (ECCC), 17:41, 2010. ECCC. 57
T HEORY OF C OMPUTING, Volume 10 (3), 2014, pp. 55–75 71
A RAM W. H ARROW, A LEXANDRA KOLLA , AND L EONARD J. S CHULMAN
[3] S ANJEEV A RORA , S UBHASH K HOT, A LEXANDRA KOLLA , DAVID S TEURER , M ADHUR T UL -
SIANI , AND N ISHEETH K. V ISHNOI : Unique Games on expanding constraint graphs are easy. In
Proc. 40th STOC, pp. 21–28. ACM Press, 2008. [doi:10.1145/1374376.1374380] 57
[4] P ER AUSTRIN: Towards sharp inapproximability for any 2-CSP. SIAM J. Comput., 39(6):2430–
2463, 2010. Preliminary version in FOCS’07. [doi:10.1137/070711670] 57
[5] M OSES C HARIKAR , KONSTANTIN M AKARYCHEV, AND Y URY M AKARYCHEV: Near-optimal
algorithms for Unique Games. In Proc. 38th STOC, pp. 205–214. ACM Press, 2006.
[doi:10.1145/1132516.1132547] 57
[6] S HUCHI C HAWLA , ROBERT K RAUTHGAMER , R AVI K UMAR , Y UVAL R ABANI , AND D. S IVAKU -
MAR : On the hardness of approximating MULTICUT and SPARSEST-CUT. Comput. Complexity,
15(2):94–114, 2006. Preliminary version in CCC’05. [doi:10.1007/s00037-006-0210-9] 57
[7] E DEN C HLAMTÁ Č , KONSTANTIN M AKARYCHEV, AND Y URY M AKARYCHEV: How to play
Unique Games using embeddings. In Proc. 47th FOCS, pp. 687–696. IEEE Comp. Soc. Press, 2006.
[doi:10.1109/FOCS.2006.36] 57
[8] T HOMAS M. C OVER AND J OY A. T HOMAS: Elements of Information Theory. Series in Telecom-
munication. John Wiley and Sons, New York, 1991. 61
[9] D IEGO D OMINICI: Asymptotic analysis of the Krawtchouk polynomials by the WKB method. The
Ramanujan Journal, 15(3):303–338, 2008. See also at arXiv. [doi:10.1007/s11139-007-9078-9] 61
[10] P ER E NFLO: On the nonexistence of uniform homeomorphisms between L p -spaces. Ark. Mat.,
8(2):103–105, 1970. [doi:10.1007/BF02589549] 56
[11] P HILIP F EINSILVER AND J ERZY KOCIK: Krawtchouk matrices from classical and quantum walks.
In Algebraic Methods in Statistics and Probability, volume 287 of Contemporary Mathematics, pp.
83–96. AMS, 2001. See also at arXiv. [doi:10.1090/conm/287] 60
[12] A DRIANO G ARSIA: A simple proof of E. Hopf’s maximal ergodic theorem. Indiana Univ. Math. J.
(J. Math. Mech.), 14(3):381–382, 1965. [doi:10.1512/iumj.1965.14.14027] 70
[13] A NUPAM G UPTA AND K UNAL TALWAR: Approximating Unique Games. In Proc. 17th Ann. ACM-
SIAM Symp. on Discrete Algorithms (SODA’06), pp. 99–106. ACM Press, 2006. [ACM:1109569]
57
[14] S UBHASH K HOT: On the power of unique 2-prover 1-round games. In Proc. 34th STOC, pp.
767–775. ACM Press, 2002. [doi:10.1145/509907.510017] 57
[15] S UBHASH K HOT, G UY K INDLER , E LCHANAN M OSSEL , AND RYAN O’D ONNELL: Optimal
inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput., 37(1):319–
357, 2007. Preliminary version in FOCS’04. See also at ECCC. [doi:10.1137/S0097539705447372]
57
T HEORY OF C OMPUTING, Volume 10 (3), 2014, pp. 55–75 72
D IMENSION -F REE L2 M AXIMAL I NEQUALITY FOR S PHERICAL M EANS IN THE H YPERCUBE
[16] S UBHASH K HOT AND O DED R EGEV: Vertex cover might be hard to approximate to within
2 − ε. J. Comput. System Sci., 74(3):335–349, 2008. Preliminary version in CCC’03.
[doi:10.1016/j.jcss.2007.06.019] 57
[17] S UBHASH K HOT AND N ISHEETH K. V ISHNOI: The Unique Games conjecture, integrality gap for
cut problems and embeddability of negative type metrics into `1 . In Proc. 46th FOCS, pp. 53–62.
IEEE Comp. Soc. Press, 2005. [doi:10.1109/SFCS.2005.74] 57
[18] B O ’ AZ K LARTAG AND O DED R EGEV: Quantum one-way communication can be exponentially
stronger than classical communication. In Proc. 43rd STOC, pp. 31–40. ACM Press, 2011. See also
at ECCC and arXiv. [doi:10.1145/1993636.1993642] 60
[19] A LEXANDRA KOLLA: Spectral algorithms for Unique Games. Comput. Complexity, 20(2):177–206,
2011. Preliminary version in CCC’10. See also at ECCC. [doi:10.1007/s00037-011-0011-7] 57
[20] A LEXANDRA KOLLA , KONSTANTIN M AKARYCHEV, AND Y URY M AKARYCHEV: How to
play Unique Games against a semi-random adversary: Study of semi-random models of Unique
Games. In Proc. 52nd FOCS, pp. 443–452. IEEE Comp. Soc. Press, 2011. See also at arXiv.
[doi:10.1109/FOCS.2011.78] 57
[21] I LIA K RASIKOV: Nonnegative quadratic forms and bounds on orthogonal polynomials. Journal of
Approximation Theory, 111(1):31–49, 2001. [doi:10.1006/jath.2001.3570] 60
[22] B EN K RAUSE: Dimension-free maximal inequalities for spherical means in the hypercube. Techni-
cal report, 2013. [arXiv:1309.4466] 59
[23] U LRICH K RENGEL: Ergodic Theorems. Walter de Gruyter, 1985. 59
[24] V LADIMIR I. L EVENSHTEIN: Krawtchouk polynomials and universal bounds for codes and designs
in Hamming spaces. IEEE Trans. Inform. Theory, 41(5):1303–1321, 1995. [doi:10.1109/18.412678]
60
[25] NATHAN L INIAL AND AVNER M AGEN: Least-distortion Euclidean embeddings of graphs:
Products of cycles and expanders. J. Combin. Theory Ser. B, 79(2):157–171, 2000.
[doi:10.1006/jctb.2000.1953] 56
[26] KONSTANTIN M AKARYCHEV AND Y URY M AKARYCHEV: How to play Unique Games on ex-
panders. In Proc. 8th Internat. Workshop on Approximation and Online Algorithms (WAOA’10), pp.
190–200, 2010. See also at ECCC. [doi:10.1007/978-3-642-18318-8_17] 57
[27] A SSAF NAOR AND T ERENCE TAO: Random martingales and localization of maximal in-
equalities. Journal of Functional Analysis, 259(3):731–779, 2010. See also at arXiv.
[doi:10.1016/j.jfa.2009.12.009] 56
[28] A MOS N EVO AND E LIAS M. S TEIN: A generalization of Birkhoff’s pointwise ergodic theorem.
Acta Mathematica, 173(1):135–154, 1994. [doi:10.1007/BF02392571] 56
T HEORY OF C OMPUTING, Volume 10 (3), 2014, pp. 55–75 73
A RAM W. H ARROW, A LEXANDRA KOLLA , AND L EONARD J. S CHULMAN
[29] P RASAD R AGHAVENDRA: Optimal algorithms and inapproximability results for every CSP? In
Proc. 40th STOC, pp. 245–254. ACM Press, 2008. [doi:10.1145/1374376.1374414] 57
[30] P RASAD R AGHAVENDRA AND DAVID S TEURER: Graph expansion and the Unique Games con-
jecture. In Proc. 42nd STOC, pp. 755–764. ACM Press, 2010. [doi:10.1145/1806689.1806792]
57
[31] E LIAS M. S TEIN: On the maximal ergodic theorem. Proc. Natl. Acad. Sci. USA, 47(12):1894–1897,
1961. PNAS. 59
[32] L UCA T REVISAN: Approximation algorithms for Unique Games. Theory of Computing, 4(5):111–
128, 2008. Preliminary version in FOCS’05. See also at ECCC. [doi:10.4086/toc.2008.v004a005]
57
[33] A NTONI Z YGMUND: On a theorem of Marcinkiewicz concerning interpolation of operations. J.
Math. Pures Appl., 9(35):223–248, 1956. 71
AUTHORS
Aram W. Harrow
Assistant Professor
Massachusetts Institute of Technology
aram mit edu
http://web.mit.edu/aram/
Alexandra Kolla
Assistant Professor
University of Illinois at Urbana-Champaign
akolla illinois edu
http://www.cs.illinois.edu/homes/akolla/
Leonard J. Schulman
Professor
California Institute of Technology
schulman caltech edu
http://users.cms.caltech.edu/~schulman/
T HEORY OF C OMPUTING, Volume 10 (3), 2014, pp. 55–75 74
D IMENSION -F REE L2 M AXIMAL I NEQUALITY FOR S PHERICAL M EANS IN THE H YPERCUBE
ABOUT THE AUTHORS
A RAM W. H ARROW graduated from M.I.T. in 2005 with a Ph. D. in physics; his advisor
was Isaac Chuang. He has since worked at the University of Bristol for five years as a
lecturer in computer science and math, and at the University of Washington as a research
professor in computer science, before returning to MIT as an assistant professor of
physics. His research focuses mainly on quantum computing, quantum information and
connections between these fields and other areas of math, physics and computer science.
A LEXANDRA KOLLA received her Ph. D. in Computer Science from U.C. Berkeley under
the supervision of Umesh Vazirani. She was a postdoc at The Institute for Advanced
Study and Microsoft Research in Redmond. Since 2012, she has been on the faculty of
the University of Illinois at Urbana Champaign. She is a fellow at the Simons Institute
in Berkeley for the academic year 2013-2014. Her research focuses mostly on spectral
graph theory, approximation algorithms, complexity theory, convex programming, and
quantum computing.
L EONARD J. S CHULMAN received the B. S. in Mathematics in 1988 and the Ph. D. in
Applied Mathematics in 1992, both from the Massachusetts Institute of Technology.
Since 2000 he has been on the faculty of the California Institute of Technology. He
has also held appointments at UC Berkeley, the Weizmann Institute of Science, the
Georgia Institute of Technology, and the Mathematical Sciences Research Institute. He
has received the MIT Bucsela prize in mathematics, an NSF mathematical sciences
postdoctoral fellowship, an NSF CAREER award, and the IEEE Schelkunoff prize. He is
the director of the Caltech Center for the Mathematics of Information, is on the faculty
of the Institute for Quantum Information and Matter, and serves as Editor-in-Chief of the
SIAM Journal on Computing. His research is in several overlapping areas: algorithms
and communication protocols; combinatorics and probability; coding and information
theory; quantum computation.
T HEORY OF C OMPUTING, Volume 10 (3), 2014, pp. 55–75 75