# Uniformity Testing over Hypergrids with Subcube Conditioning

Xi Chen
Columbia University
<EMAIL_ADDRESS>Cassandra Marcussen
Harvard University
<EMAIL_ADDRESS>
###### Abstract

We give an algorithm for testing uniformity of distributions supported on
hypergrids $[m_{1}]\times\cdots\times[m_{n}]$, which makes
$\smash{\widetilde{O}(\text{poly}(m)\sqrt{n}/\epsilon^{2})}$ many queries to a
subcube conditional sampling oracle with $m=\max_{i}m_{i}$. When $m$ is a
constant, our algorithm is nearly optimal and strengthens the algorithm of
[CCK+21] which has the same query complexity but works for hypercubes $\\{\pm
1\\}^{n}$ only.

A key technical contribution behind the analysis of our algorithm is a proof
of a robust version of Pisier’s inequality for functions over hypergrids using
Fourier analysis.

###### Contents

  1. 1 Introduction
    1. 1.1 Our Contributions
    2. 1.2 Proof Overview and Comparison with Previous Work
      1. 1.2.1 A Robust Pisier’s Inequality for Hypergrids
      2. 1.2.2 Proof of Theorem 6
    3. 1.3 Background and Related Work
    4. 1.4 Notation
  2. 2 The Algorithm
  3. 3 Robust Pisier’s Inequality on Hypergrids
    1. 3.1 Fourier Analysis over Hypergrids
    2. 3.2 Proof of the Robust Pisier’s Inequality over Hypergrids
  4. 4 Proof of Lemma 9
    1. 4.1 Connecting Total Variation Distance to Directed Graphs
    2. 4.2 Separating into Cases
    3. 4.3 From Directed Graphs to the Bias Vector
    4. 4.4 Case 1: Graph with Uneven Edges
    5. 4.5 Case 2: Graph with Even Edges
  5. 5 Mean Testing over Hypergrids
  6. 6 Discussion and Open Problems
  7. A Additional Proofs

##  1 Introduction

Much of today’s data can be thought of as samples from an unknown probability
distribution over a large and high-dimensional sample space. Testing global
properties of a distribution [CDVV14, VV14, Pan08, DK16, DKN14] on such a
space, however, is known to be intractable under the classical statistical
model where an algorithm can only draw independent samples from the unknown
distribution. This holds even for testing the property of _uniformity_
111Given an unknown distribution $p$ over a sample space $\Sigma$, accept with
probability at least $2/3$ when $p$ is uniform over $\Sigma$ and reject with
probability at least $2/3$ when $p$ is $\epsilon$-far from the uniform
distribution in total variation distance., for which we know that
$\Theta(\sqrt{|\Sigma|}/\epsilon^{2})$ samples are both sufficient and
necessary [Pan08, VV14]. So for high-dimensional sample spaces such as $\\{\pm
1\\}^{n}$ or $[{m_{1}}]\times\dots\times[{m_{n}}]$, the number of samples
needed under the classical statistical model scales exponentially in $n$. To
circumvent the intractability, recent work has proceeded by either restricting
the class of input distributions (e.g., restricting $p$ to be a product
distribution [CDKS16]), or by allowing stronger oracle access to $p$. The goal
of both approaches is to develop algorithms that scale polynomially or even
sublinearly in the dimension $n$ under certain well-motivated assumptions.

One of the most natural models in the latter direction is the _subcube
conditioning model_ , which is particularly suitable for high-dimensional
distributions [CRS12, BC17, CCK+21, CJLW20]. The model was suggested in
[CRS12] and first studied in [BC17] (more discussion on the model and related
work can be found in Section 1.3). For the general space of
$[{m_{1}}]\times\dots\times[{m_{n}}]$, subcube conditional query access allows
algorithms to specify a subgrid of $[m_{1}]\times\dots\times[m_{n}]$ by giving
a restriction $\rho$ with $\rho_{i}\in[m_{i}]\cup\\{*\\}$ for each $i\in[n]$
and requesting a sample from the distribution conditioned222When conditioned
on a subcube with zero support, one may consider models where the oracle
returns either a uniform sample or outputs “error.” We note that our algorithm
will never run into this scenario. on the sample lying in the subgrid
specified by $\rho$ (i.e., the set of
$x\in[{m_{1}}]\times\dots\times[{m_{n}}]$ with $x_{i}=\rho_{i}$ for all
$i\in[n]$ such that $\rho_{i}\neq*$).

Recently, [CCK+21] gave an algorithm for testing uniformity over hypercubes
$\\{\pm 1\\}^{n}$, which makes $\tilde{O}(\sqrt{n}/\epsilon^{2})$ queries to a
subcube conditional sampling oracle. The algorithm is nearly optimal (given
the $\Omega(\sqrt{n}/\epsilon^{2})$ lower bound of [CDKS16, DDK16] for testing
uniformity of product distributions under the classical statistical model,
which was observed in [BC17] to carry over to subcube conditional sampling). A
drawback of their algorithm, however, is that it only works for hypercubes
$\\{\pm 1\\}^{n}$.

_In this paper, we study the problem of testing uniformity of distributions
over the general hypergrid domain $[m_{1}]\times\dots\times[{m_{n}}]$ under
the subcube conditioning model._ There are a number of compelling reasons to
study this problem. From a practical perspective, testing algorithms for
hypercubes are not applicable in scenarios when the variables / features are
not Boolean. And natural attempts to reduce the problem over
$[{m_{1}}]\times\dots\times[{m_{n}}]$ directly to that over hypercubes do not
seem to work either because the total variation distance is not preserved or
the subcube conditional oracle does not cope with the reduction. (For the
latter consider the reduction from $[4]^{n}$ to $\\{\pm 1\\}^{2n}$ by encoding
each entry of $[4]$ using two bits. While the total variation distance is
preserved, subcube conditional oracles for distributions over $\\{\pm
1\\}^{2n}$ cannot be simulated using those for $[4]^{n}$. The former
corresponds to a more powerful oracle where an algorithm can, e.g., fix a
coordinate to be in $\\{1,3\\}$.)

From a theoretical perspective, the problem is well-motivated due to a number
of obstacles that one needs to be overcome to generalize the prior work of
[CCK+21] from hypercubes to hypergrids. (More discussion and a comparison of
our work with that of [CCK+21] can be found in Section 1.2.) One of the
primary challenges is that their analysis of correctness crucially relies on a
_robust_ version of Pisier’s inequality. The latter is an inequality from
convex analysis that relates the $\ell_{s}$-norm of a function $f$ over
$\\{\pm 1\\}^{n}$ to its $i$th coordinate Laplacian operator $L_{i}f$ (see
definition below), and it was not known whether a similar inequality holds for
functions over hypergrids $[m_{1}]\times\dots\times[m_{n}]$.

###  1.1 Our Contributions

We study uniformity testing over hypergrids $[m_{1}]\times\dots\times[m_{n}]$
with $m_{i}\geq 2$ for all $i$. Let $m=\max_{i\in[n]}m_{i}$. Our main result
is an algorithm that makes
$\smash{\tilde{O}(\text{poly}(m)\sqrt{n}/\epsilon^{2})}$ many subcube
conditional queries:

######  Theorem 1 (Uniformity Testing).

There is an algorithm which, given $n,m_{1},\ldots,m_{n}$ and subcube
conditional query access to a distribution $p$ supported on
$[m_{1}]\times\dots\times[m_{n}]$ and a distance parameter $\epsilon\in(0,1)$,
makes $\tilde{O}(m^{21}\sqrt{n}/\epsilon^{2})$ queries and can distinguish
with probability at least $2/3$ between the case when $p$ is uniform, and when
$p$ is $\epsilon$-far from uniform in total variation distance.

Our algorithm improves the algorithm of [CCK+21] which only works for
hypercubes, and is nearly optimal when $m$ is a constant. For general $m$, the
best-known lower bound for the problem is $\Omega(\sqrt{nm}/\epsilon^{2})$
[BGKV21] (again, via the connection to uniformity testing of product
distributions under the statistical model). While we believe that the
polynomial $m^{21}$ in Theorem 1 can be improved by tightening up our
analysis, it remains an important open question to pin down the complexity as
a function of $n,m$ and $\epsilon$.

We sketch the proof of Theorem 1 in Section 1.2. One of the main contributions
of our paper is the proof of a robust version of Pisier’s inequality for
functions over hypergrids, which plays a crucial role in the analysis of the
main algorithm and may be of independent interest. (We review and compare with
the original Pisier’s inequality [Pis06] in Section 1.2.1.) We need some
notation to state the inequality. Since Fourier analysis will be used heavily
in the proof of the inequality, from now on we will always use

$\mathbb{Z}_{M}:=\mathbb{Z}_{m_{1}}\times\dots\times\mathbb{Z}_{m_{n}},$

where $M=(m_{1},\ldots,m_{n})$, to denote the hypergrid. Given
$x\in\mathbb{Z}_{M}$, $i\in[n]$ and $a\in\mathbb{Z}_{m_{i}}$, let $x^{(i)\to
a}$ denote the vector obtained from $x$ by replacing $x_{i}$ with $a$. Given
any function $f:\mathbb{Z}_{M}\rightarrow\mathbb{C}$, the $i$th coordinate
Laplacian operator is defined as

$L_{i}f(x)=f(x)-\mathbb{E}_{a\sim\mathbb{Z}_{m_{i}}}\big{[}f(x^{(i)\rightarrow
a})\big{]}.$

For each $j\in[n]$, let $\mathbb{Z}_{m_{j}}^{*}=\\{1,\ldots,m_{j}-1\\}$, and
let $\omega_{j}=e^{2\pi i/m_{j}}$ be the primitive $m_{j}$-th root of unity.

We are ready to state the new Pisier’s inequality for hypergrids. The robust
version is more involved; we state and discuss it later in Section 1.2.1.

######  Theorem 2 (Pisier’s Inequality for Hypergrids).

Let $f:\mathbb{Z}_{M}\to\mathbb{C}$ be a function with
$\mathbb{E}_{x\sim\mathbb{Z}_{M}}[f(x)]=0$. Then, for any $s\in[1,\infty)$ we
have

$\displaystyle\Big{(}\mathbb{E}_{x\sim\mathbb{Z}_{M}}\big{[}\left\lvert
f(x)\right\rvert^{s}\big{]}\Big{)}^{1/s}\leq O(\log
n)\cdot\left(\mathbb{E}_{x,y\sim\mathbb{Z}_{M}}\left[\left\lvert\sum_{i\in[n]}L_{i}f(x)\sum_{a\in\mathbb{Z}_{m_{i}}^{*}}\omega_{i}^{-ay_{i}}\omega_{i}^{ax_{i}}\right\rvert^{s}\right]\right)^{1/s}.$

One should interpret Pisier’s inequality as providing a way of connecting the
$\ell_{s}$-norm of the function $f$ to its Laplacian operators. Within the
context of how the inequality is used in this paper, Laplacian operators
capture the difference in the function value along edges of the hypergrid
(that is, between $x$ and $x^{(i)\to a}$). The extension of Pisier’s
inequality to hypergrids could have applications in other problems where the
$\ell_{s}$-norm needs to be connected to edge-wise differences of a function
defined over $\mathbb{Z}_{M}$.

###  1.2 Proof Overview and Comparison with Previous Work

First we recall the notion of restrictions and projections of a distribution.
Given a restriction $\rho$ with $\rho_{i}$ $\in\mathbb{Z}_{m_{i}}\cup\\{*\\}$
for each $i\in[n]$, we write $\text{stars}(\rho)$ to denote the set of
$i\in[n]$ with $\rho_{i}=*$ and denote by $p_{|\rho}$ the distribution of
${x}_{\text{stars}(\rho)}$ with ${x}$ drawn from $p$ conditioned on
$x_{i}=\rho_{i}$ for every $i\notin\text{stars}(\rho)$. The other operation on
distributions is projections: Given $S\subseteq[n]$, $p_{S}$ denotes the
distribution of $x_{S}$ with $x\sim p$.

######  Definition 3 (Random Restrictions).

Given $\sigma\in[0,1]$, we let $\mathcal{S}_{\sigma}$ denote the distribution
supported on subsets of $[n]$ where $S\sim\mathcal{S}_{\sigma}$ includes each
$i\in[n]$ independently with probability $\sigma$. Given a distribution $p$
supported on $\mathbb{Z}_{M}$, we use $\mathcal{D}_{\sigma}(p)$ to denote the
following distribution of restrictions: to draw a restriction
$\rho\sim\mathcal{D}_{\sigma}(p)$, we first sample a set
$\smash{S\sim\mathcal{S}_{\sigma}}$ and an $x\sim p$; then, $\rho_{i}$ for
each $i\in[n]$ is set to be

$\displaystyle\rho_{i}=\begin{cases}*&\text{if }i\in{S}\\\ {x}_{i}&\text{if
}i\notin{S}\end{cases}.$ (1)

Given a distribution $p$ over $\mathbb{Z}_{M}$, we define the following bias
vector that generalizes the mean vector of a distribution over
$\\{-1,1\\}^{n}$:

######  Definition 4 (Bias Vector).

Let $p$ be a distribution over $\mathbb{Z}_{M}$, $i\in[n]$ and
$c,d\in\mathbb{Z}_{m_{i}}$. We define

$\mu^{c,d}_{i}(p)=\frac{\Pr_{x\sim p}[x_{i}=c]-\Pr_{x\sim
p}[x_{i}=d]}{\Pr_{x\sim p}[x_{i}=c]+\Pr_{x\sim p}[x_{i}=d]}.$

When $\Pr_{x\sim p}[x_{i}=c]=\Pr_{x\sim p}[x_{i}=d]=0$, the bias
$\mu_{i}^{c,d}(p)$ is set to be $0$ by default. We also allow $c=d$ for
notational convenience, in which case $\smash{\mu_{i}^{c,d}(p)=0}$ trivially.

Moreover, we write $\mu(p)$ to denote the _bias vector_ of $p$: $\mu(p)$ has
$\sum_{i\in[n]}m_{i}^{2}$ entries $\mu_{i}^{c,d}(p)$ and thus,

$\big{\|}\mu(p)\big{\|}_{2}=\sqrt{\sum_{i\in[n]}\sum_{c,d\in\mathbb{Z}_{m_{i}}}\left(\mu^{c,d}_{i}(p)\right)^{2}}.$

The intuition behind our uniformity testing algorithm is similar to the
algorithm of [CCK+21], which is inspired by Lemma 5 and Theorem 6 below:

######  Lemma 5.

Let $p$ be a distribution over $\mathbb{Z}_{M}$. Then for any
$\sigma\in[0,1]$, we have333We write $\mathcal{U}$ to denote the uniform
distribution, and $d_{TV}$ to denote the total variation distance.

$d_{TV}(p,\mathcal{U})\leq\mathbb{E}_{S\sim\mathcal{S}_{\sigma}}\big{[}d_{TV}(p_{\overline{S}},\mathcal{U})\big{]}+\mathbb{E}_{\rho\sim\mathcal{D}_{\sigma}(p)}\big{[}d_{TV}(p_{|\rho},\mathcal{U})\big{]}.$

######  Theorem 6.

Let $p$ be a distribution over $\mathbb{Z}_{M}$. Then for any
$\sigma\in[0,1]$, we have

$\mathbb{E}_{\rho\sim\mathcal{D}_{\sigma}(p)}\left[\left\|\mu(p_{|\rho})\right\|_{2}\right]\geq\frac{\sigma}{m^{7.5}\cdot\emph{\text{polylog}}(nm)}\cdot\tilde{\Omega}\left(\mathbb{E}_{S\sim\mathcal{S}_{\sigma}}\big{[}d_{TV}(p_{\overline{S}},\mathcal{U})\big{]}-2e^{-\min(\sigma,1-\sigma)n/10}\right).$

Lemma 5 extends a corresponding lemma from [CCK+21] for distributions
supported on $\\{-1,1\\}^{n}$ to distributions supported on hypergrids. The
proof can be found in Appendix A. Theorem 6, on the other hand, is the main
technical result of the paper, which we discuss in the rest of the subsection.
But before that, assuming Lemma 5 and Theorem 6, our main uniformity testing
algorithm SubCondUni proceeds as follows (see Section 2 for details): consider
a distribution $p$ over $\mathbb{Z}_{M}$ with
$d_{TV}(p,\mathcal{U})\geq\epsilon$ and let $\sigma$ be sufficiently small; it
will be set to be $1/\text{polylog}(1/\epsilon)$ in the proof. Then by Lemma
5, one of the following two cases must hold:

  1. 1.

$\mathbb{E}_{\rho\sim\mathcal{D}_{\sigma}(p)}[d_{TV}(p_{|\rho},\mathcal{U})]\geq\epsilon/2$:
In this case, a typical draw of $\rho\sim\mathcal{D}_{\rho}(p)$ satisfies the
property that $d_{TV}(p_{|\rho},\mathcal{U})$ remains large and the dimension
$|\text{stars}(\rho)|$ of $p_{|\rho}$ is much smaller than $n$ (i.e.,
$\approx\sigma n$). This case is handled using recursive calls to SubCondUni
on $p_{|\rho}$ with $\rho\sim\mathcal{D}_{\rho}(p)$.

  2. 2.

$\mathbb{E}_{S\sim\mathcal{S}_{\sigma}}[d_{TV}(p_{\overline{S}},\mathcal{U})]\geq\epsilon/2$:
Theorem 6 implies that a typical $\rho\sim\mathcal{D}_{\rho}(p)$ has a bias
vector with a large $\ell_{2}$-norm. This case is handled by
ProjectedTestMean, a subroutine we give in Section 5 to decide whether a given
distribution is uniform or has a bias vector with a large $\ell_{2}$-norm.

The performance guarantee of ProjectedTestMean is summarized in the following
theorem:

######  Theorem 7.

There is an algorithm ProjectedTestMean which, given $n$,
$M=(m_{1},\ldots,m_{n})$, $\epsilon>0$ and sample access to a probability
distribution $p$ over $\mathbb{Z}_{M}$, draws

$O\big{(}m^{4}\log(mn)\big{)}\cdot\max\left\\{\frac{1}{\epsilon^{2}\sqrt{n}},\frac{1}{\epsilon}\right\\}.$

many samples $x\sim p$ and satisfies the following properties:

  1. 1.

If $p$ is the uniform distribution, the algorithm outputs accept with
probability at least $2/3$; and

  2. 2.

If $p$ satisfies $\|\mu(p)\|_{2}\geq\epsilon\sqrt{n}$, the algorithm outputs
reject with probability at least $2/3$.

ProjectedTestMean generalizes the MeanTester algorithm of [CCK+21] to work on
distributions over hypergrids instead of just hypercubes. While it essentially
reduces the task to the same task over hypercubes and passes it down to
MeanTester, a few new ingredients are needed for the reduction to work. These
include a preprocessing step (using a so-called CoarseTest) and a method to
project the input distribution over $\mathbb{Z}_{M}$ to a small number of
distributions over the hypercube, on which we run MeanTester. We present
ProjectedTestMean and its analysis in Section 5.

We discuss the proof of Theorem 6 in the rest of the overview.

####  1.2.1 A Robust Pisier’s Inequality for Hypergrids

The most important ingredient we need in the proof of Theorem 6 is a _robust_
version of Pisier’s inequality for hypergrids. Pisier’s inequality was first
introduced in the paper [Pis06], and is an important result within the realm
of convex analysis:

######  Theorem 8 (Pisier’s inequality [Pis06]).

Let $f:\\{\pm 1\\}^{n}\to\mathbb{R}$ be a function with
$\mathbb{E}_{x}[f(x)]=0$. Then,

$\mathbb{E}_{x\sim\\{\pm 1\\}^{n}}\big{[}\left\lvert
f(x)\right\rvert\big{]}\leq O(\log n)\cdot\mathbb{E}_{x\sim\\{\pm
1\\}^{n}}\left[\left\lvert\sum_{i\in[n]}y_{i}x_{i}L_{i}f(x)\right\rvert\right].$

Alternative proofs of Pisier’s inequality can be found in [NS02, BM87]. Before
this work we are not aware of any generalization of Pisier’s inequality beyond
the domain of hypercubes. The flow of our proof of Theorem 7, Pisier’s
inequality over hypergrids, at a high level follows that of [NS02]. The
challenge lies in careful considerations required when moving from the use of
Fourier analysis on hypercubes, where functions in the basis are $\\{\pm
1\\}$-valued, to Fourier analysis on hypergrids, where functions in the basis
take complex values that are roots of unity. In particular, more intricate
expressions needed to be discovered (e.g., in Lemma 14) in order to obtain
cancellations that help connect the $\ell_{s}$-norm of $f$ with its Laplacian
operators.

As mentioned earlier, Theorem 2 is not sufficient for our purpose of proving
Theorem 6 but we need a more powerful, robust version of Pisier’s inequality
for hypergrids. Additional definitions are needed to state the inequality so
we delay it to Section 3 (Theorem 11) where it is proved. The notion of
robustness is the same as in [KMS18] and [CCK+21]: in the original Pisier’s
inequality such as Theorem 8 and 2, difference in the function value along
each edge $\\{x,x^{(i)\to a}\\}$ is accounted twice on the RHS, once at $x$
and once at $x^{(i)\to a}$; in the robust version, imagine that an adversary
gets to pick any orientation of edges and the same inequality still needs to
hold when each directed edge $(x,x^{(i)\to a})$ (oriented by the adversary
from $x$ to $x^{(i)\to a}$) is only accounted once at $x$ (but not at
$x^{(i)\to a}$). This robustness will be crucial when we apply the inequality
to prove Theorem 6, which we discuss in Section 1.2.2.

The key observation behind the proof of our robust Pisier’s inequality for
hypergrids is similar to that of [CCK+21] for hypercubes: at one point of the
proof of the original inequality, the expectation where every edge of the
hypergrid is accounted twice (once for each of its vertices) can be replaced
by a similar expectation where every edge is accounted once with respect to a
given orientation of edges. Again, the need to work with Fourier analysis over
$\mathbb{Z}_{M}$ and deal with roots of unity makes the analysis much more
demanding. Indeed the inequality we prove takes a more complex form on the RHS
compared to Theorem 2; in contrast, the robust Pisier’s inequality for
hypercubes of [CCK+21] looks identical to Theorem 8.

####  1.2.2 Proof of Theorem 6

We start with some notation. Let $\mathcal{S}(t)$ be the uniform distribution
supported on all subsets of $[n]$ of size $t$. Given a distribution $p$ over
$\mathbb{Z}_{M}$, we let $\mathcal{D}(t,p)$ be the following distribution over
restrictions: to draw $\rho\sim\mathcal{D}(t,p)$, we first sample $y\sim p$
and $S\sim\mathcal{S}(t)$ and then set $\rho$ to be $\rho_{i}=*$ if $i\in S$
and $\rho_{i}=y_{i}$ if $i\notin S$.

We are now ready to state the main technical lemma, which is proved in Section
4:

######  Lemma 9.

Let $p$ be a distribution over $\mathbb{Z}_{M}$, $t\in[n-1]$, and denote

$\alpha:=\mathbb{E}_{T\sim\mathcal{S}(t)}\big{[}d_{TV}(p_{\overline{T}},\mathcal{U})\big{]}\geq
0.$

Then we have

$\displaystyle\mathbb{E}_{\rho\sim\mathcal{D}(t,p)}\Big{[}\left\|\mu(p_{|\rho})\right\|_{2}\Big{]}+\mathbb{E}_{\rho\sim\mathcal{D}(t+1,p)}\Big{[}\left\|\mu(p_{|\rho})\right\|_{2}\Big{]}\geq\frac{t}{n}\cdot\frac{\alpha}{m^{7.5}\cdot\mathrm{polylog}(nm/\alpha)}.$
(2)

A significant portion of the paper is dedicated to proving Lemma 9 in Section
4. Once Lemma 9 is proven, it only requires a short proof to obtain Theorem 6.
The proof of Theorem 6 assuming Lemma 9 is very similar to an argument used in
[CCK+21], except for a minor change. It is included in Appendix A for
completeness. Below we sketch the proof of Lemma 9 and compare it with
[CCK+21].

The key step of the proof of Lemma 9 is the construction of a family of
directed graphs that is used to connect $d_{TV}(p_{\overline{T}},\mathcal{U})$
of $T\sim\mathcal{S}(t)$ with $\|\mu(p_{|\rho})\|_{2}$ of either
$\rho\sim\mathcal{D}(t,p)$ or $\sim\mathcal{D}(t+1,p)$. In more details, let
$T\subset[n]$ be a set of size $t$ and let $K=M_{\overline{T}}$ (so
$p_{\overline{T}}$ is a distribution over the hypergrid $\mathbb{Z}_{K}$). Let
$\mathcal{H}(T)$ denote the undirected graph over $\mathbb{Z}_{K}$ with
undirected edges $\\{x,x^{(i)\to b}\\}$ for all
$x\in\mathbb{Z}_{K},i\in\overline{T}$ and $b\neq x_{i}$. Using values of
$p_{\overline{T}}(x)$, we classify edges of $\mathcal{H}(T)$ into those that
are _uneven_ and _even_. Roughly speaking, an edge $\\{x,y\\}$ of
$\mathcal{H}(T)$ is uneven if

$\max\big{(}p_{\overline{T}}(x),p_{\overline{T}}(y)\big{)}\gg\min\big{(}p_{\overline{T}}(x),p_{\overline{T}}(y)\big{)}$

and is even otherwise. The most important step of the proof is the
construction of an orientation $G(T)$ of $\mathcal{H}(T)$, where different
strategies are used to orient uneven edges and even edges.

Once the directed graphs $G(T)$ for each $T$ is in place, the proof of Lemma 9
proceeds as follows:

  1. 1.

In Section 4.1, we apply the robust Pisier’s inequality on $s=1$ and $f$ over
$\mathbb{Z}_{K}$ set to be

$f(x)=p_{\overline{T}}(x)\prod_{j\in\overline{T}}m_{j}-1$

so the expectation of $f$ is $0$ and the LHS of the inequality is exactly
$d_{TV}(p_{\overline{T}},\mathcal{U})$. Orienting the edges using $G(T)$, the
inequality implies that either the expectation of

$\sqrt{\text{number of outgoing uneven edges of $x$}}$ (3)

or the expectation of

$\sqrt{\text{number of outgoing even edges of $x$}}$ (4)

when $x\sim p_{\overline{T}}$ is large in terms of
$d_{TV}(p_{\overline{T}},\mathcal{U})$.

  2. 2.

On the other hand, in Section 4.3, 4.4 and 4.5, we connect $G(T)$ with
$\|\mu(p_{|\rho})\|_{2}$ by showing that when either the expectation of (3) or
the expectation of (4) is large for a typical $T\sim\mathcal{S}(t)$, it
implies that $\|\mu(p_{|\rho})\|_{2}$ is large for a typical $\rho$ drawn
either from $\mathcal{D}(t,p)$ or $\mathcal{D}(t+1,p)$. The two cases of (3)
and (4) are handled separately in Section 4.4 and 4.5, respectively.

Compared to that of a similar lemma in [CCK+21], our proof of Lemma 9 differs
significantly in the construction of directed graphs $G(T)$ due to the simple
fact a vertex in $\mathcal{H}(T)$ has multiple edges along the same variable
(while in hypercubes, every vertex has a unique edge along each variable). In
particular, the orientation of even edges needs to be handled with a more
delicate strategy. In [CCK+21], uneven and even edges are oriented separately;
in contrast, the orientation of even edges here crucially depends on that of
uneven edges (uneven edges are handled first, followed by even edges). The
analysis in Case 2 (Section 4.5), which becomes more involved compared to
[CCK+21], only works with the new orientation strategy for even edges.

###  1.3 Background and Related Work

Distribution testing: Distribution testing — initially studied in [GR11],
[BFR+00], and [BFR+13] — is concerned with determining whether a distribution
satisfies a certain property or is far from satisfying the property. Sample-
optimal algorithms are known for a range of problems in distribution testing
in the standard setting, where samples are drawn independently from the
probability distribution that is being tested. For example, [CDVV14, VV14,
Pan08, DK16, DKN14] give algorithms for testing with optimal sample
complexity. The sample complexity lower bounds for many such problems have a
polynomial dependence on the domain size, which in the high-dimensional
setting leads to an exponential dependence on the dimension. Therefore, in
this setting, newer models of sampling or testing are needed to achieve an
improved (ideally sublinear) dependence on the dimension.

Property testing on extended high-dimensional domains: Property testing on
extended high-dimensional domains $[m]^{n}$, also known as hypergrids, is
fruitful to study due to its potential to yield sample complexity bounds that
depend explicitly on both the alphabet size $m$ and the dimension $n$. The
goal of this research is typically to construct algorithms with a polynomial
(or even sublinear) dependence on $n$ and a polynomial dependence on $m$. Many
of the algorithms or sample complexity lower-bounds for testing properties of
functions or distributions over hypergrids rely on Fourier analysis. For
example, in [BRY14], Blais, Raskhodnikova, and Yaroslavtsev utilize a set of
Walsh functions, a canonical Fourier basis for functions on the line $[m]$, in
their analysis. Other papers such as [BCS17] and [HY20] also apply Fourier
analysis by using Walsh functions over $[m]^{n}$. One advantage of Walsh
functions is that they are $\\{\pm 1\\}$-valued. However, Walsh functions can
only be used as a Fourier basis if $m$ is a power of $2$. In this paper, we
consider the high-dimensional domain
$\mathbb{Z}_{m_{1}}\times\dots\times\mathbb{Z}_{m_{n}}$ and use certain powers
of the primitive $m$-th root of unity to form the Fourier basis, which allows
us to avoid this restriction to powers of $2$.

Other papers on testing properties over hypergrids $[m]^{n}$ include [CS13,
CS12, ADK15, AJMR12].

Subcube conditioning: As mentioned earlier, under the standard sampling model,
$\sqrt{|\Sigma|}/\epsilon^{2}$ samples are needed for testing uniformity
[Pan08, VV14]. To circumvent this issue under the high-dimensional setting,
one may choose to consider distributions with more structure; for example,
product distributions [CDKS16]. On the other hand, one may study query models
with stronger access to the distribution. The subcube conditioning oracle
model was studied with the latter purpose, and was first introduced in [CRS12]
and studied in [BC17].

In [CCK+21], the authors give a nearly-optimal uniformity testing algorithm
for distributions supported on hypercubes $\\{\pm 1\\}^{n}$ under the subcube
conditioning model. The subcube conditioning oracle model has also been used
in studying the problems of learning and testing junta distributions on
$\\{\pm 1\\}^{n}$ with respect to the uniform distribution [CJLW20].

The subcube conditioning model is a theoretical model, but not an artificial
model. Subcube conditional samples provide stronger access to the underlying
distribution that is also potentially practically realizable. Subcube
conditioning has received recent attention beyond the field of property
testing, for example in [BLMT23]. In [BLMT23], the authors study how subcube
conditioning can be used to convert PAC learning algorithms that work under
the uniform distribution into ones that works under an arbitrary and unknown
distribution.

Other recent papers have used variations of the subcube conditioning model to
study the problem of identity testing. In [BCŠV22], the authors prove that if
approximate tensorization holds for the visible distribution $\mu$ over
$[k]^{n}$, then there is an efficient identity testing algorithm for any
hidden distribution $\pi$ using $\tilde{O}(n/\epsilon)$ queries to the so-
called coordinate oracle. The latter is similar to the subcube oracle, with
the added restriction that all but one coordinate must be fixed when taking a
random restriction.

More broadly, the subcube conditioning model is an adaptation of the
conditional sampling model. The original and more general conditional sampling
model [CFGM13, CFGM16, CRS14, CRS12] allows for the algorithm to specify an
arbitrary subset of a domain and receive a sample that is conditioned on it
lying in the subset. This conditional sampling model has been applied to a
range of problems in distribution testing and beyond in order to circumvent
lower bounds in the standard sampling model.

###  1.4 Notation

We use $\tilde{O}(f(n))$ to denote $O(f(n)\cdot\text{polylog}(f(n)))$ and
$\tilde{\Omega}(f(n))$ to denote $\Omega(f(n)/(1+|\text{polylog}(f(n))|))$. We
write $f(n)\lesssim g(n)$ if, for some constant $c>0$, $f(n)\leq c\cdot g(n)$
for all $n\geq 0$. $\gtrsim$ is defined similarly.

Given $M=(m_{1},\ldots,m_{n})$, we write $\mathbb{Z}_{M}$ to denote
$\mathbb{Z}_{m_{1}}\times\dots\times\mathbb{Z}_{m_{n}}$. We will occasionally
denote

${\bigtimes_{i\in[n]}[m_{i}]}:={[m_{1}]\times\dots\times[m_{n}]}\quad\text{\
and\
}\quad\bigtimes_{i\in[n]}\mathbb{Z}_{m_{i}}:={\mathbb{Z}_{m_{1}}\times\dots\times\mathbb{Z}_{m_{n}}}.$

Given $x\in\\{-1,1\\}^{n}$, we write $x^{(i)}$ to denote the string that is
identical to $x$ but with coordinate $i$ flipped, i.e.
$\smash{x_{j}^{(i)}=x_{j}}$ for all $j\neq i$ and
$\smash{x_{i}^{(i)}=-x_{i}}$. Given $x\in\mathbb{Z}_{M}$, $i\in[n]$ and
$a\in\mathbb{Z}_{m_{i}}$, we let $x^{(i)\to a}$ denote the vector that is
identical to $x$ but with coordinate $i$ set to $a$, i.e. $\smash{x^{(i)\to
a}_{j}=x_{j}}$ for all $j\neq i$ and $\smash{x^{(i)\to a}_{i}}=a$.

##  2 The Algorithm

In this section we present our main testing algorithm, SubCondUni, and use it
to prove Theorem 1. It is presented as Algorithm 1 and uses ProjectedTestMean
as a subroutine.

1:Dimension $n$, $M=(m_{1},\ldots,m_{n})$, subcube access to distribution $p$
over $\mathbb{Z}_{M}$, and $\epsilon\in(0,1/2]$

2:if $n$ and $\epsilon$ violate (6) then

3: Run an algorithm (Lemma 4.20) from [BCŠV22]) and return the same answer

4:end if

5:StartMainCase$\triangleright$ Main case: (6) satisfied

6: Let $m=\max_{i}m_{i}$ and let $\smash{L=L(n,\epsilon)}$ be as defined in
(10)

7: for $j=1,2,\dots,\lceil\log 2L\rceil$ do $\triangleright$ Handle the first
case of (8)

8: Sample $s_{j}=8L\log(2L)\cdot 2^{-j}$ restrictions from
$\mathcal{D}_{\sigma}(p)$

9: for each restriction $\rho$ sampled with $|\text{stars}(\rho)|>0$ do

10: Run
$\textsc{ProjectedTestMean}(|\text{stars}(\rho)|,M_{\text{stars}(\rho)},2^{-j},p_{|\rho})$
for $r=O(\log(nm/\epsilon))$ times

11: return reject if the majority of calls return reject

12: end for

13: end for

14: for $j=1,2,\dots,\lceil\log(4/\epsilon)\rceil$ do $\triangleright$ Handle
the second case of (8)

15: Sample $s_{j}^{\prime}=(32/\epsilon)\log(4/\epsilon)\cdot 2^{-j}$
restrictions from $\mathcal{D}_{\sigma}(p)$

16: for each restriction $\rho$ sampled that satisfies
$0<|\text{stars}(\rho)|\leq 2\sigma n$ do

17: Let
$M_{\text{stars}(\rho)}=(m_{i_{1}},m_{i_{2}},\dots,m_{i_{|\text{stars}(\rho)|}})$
where each $i_{k}\in\text{stars}(\rho)$

18: Run
$\textsc{SubCondUni}(|\text{stars}(\rho)|,M_{\text{stars}(\rho)},2^{-j},p_{|\rho})$
for $t=100\log(16/\epsilon)$ times

19: return reject if the majority of calls return reject

20: end for

21: end for

22: return accept

23:EndMainCase

Algorithm 1 $\textsc{SubCondUni}(n,M,\epsilon,p)$

This algorithm proceeds in a similar fashion as the SubCondUni algorithm in
[CCK+21]. Let $p$ be a distribution over $\mathbb{Z}_{M}$ with
$M=(m_{1},\ldots,m_{n})$ (where each $m_{i}\geq 2$). Let

$\sigma:=\sigma(\epsilon)=\frac{1}{C_{0}\cdot\log^{4}(16/\epsilon)}$ (5)

where $C_{0}>0$ is a sufficiently large constant to be specified later. If $n$
and $\epsilon$ violate

$e^{-\sigma n/10}\leq\epsilon/8,$ (6)

i.e., $\epsilon$ is tiny, we use a result from [BCŠV22]. Given the violation
of (6), we have

$n=O\left(\frac{1}{\sigma}\cdot\log\left(\frac{1}{\epsilon}\right)\right)=O\left(\log^{5}\left(\frac{1}{\epsilon}\right)\right).$
(7)

It follows from Theorem 4.1 and Lemma 4.20 of [BCŠV22] that uniformity can be
tested with $\widetilde{O}({n\sqrt{m}}/{\epsilon^{2}})$ samples in this case.
(To use Theorem 4.1 and Lemma 4.20 in [BCŠV22], note that the uniform
distribution is $\nu=({1}/{m})$-balanced and satisfies approximate
tensorization of entropy with constant $C=1$.)

From now on we focus on the general case where $n$ and $\epsilon$ satisfy (6).
To better understand how the algorithm works, consider the case when
$d_{TV}(p,\mathcal{U})\geq\epsilon$. Lemma 5 implies that either

$\mathbb{E}_{S\sim\mathcal{S}_{\sigma}}\big{[}d_{TV}(p_{\overline{S}},\mathcal{U})\big{]}\geq\epsilon/2\quad\text{\
or\
}\quad\mathbb{E}_{\rho\sim\mathcal{D}_{\sigma}(p)}\left[d_{TV}(p_{|\rho},\mathcal{U})\right]\geq\epsilon/2.$
(8)

Assuming
$\mathbb{E}_{S\sim\mathcal{S}_{\sigma}}[d_{TV}(p_{\overline{S}},\mathcal{U})]\geq\epsilon/2$,
using $e^{-\sigma n/10}\leq\epsilon/8$ and
$\sigma=1/\text{polylog}(1/\epsilon)$, Theorem 6 gives

$\mathbb{E}_{\rho\sim\mathcal{D}_{\sigma}(p)}\left[\frac{1}{m\sqrt{n}}\left\|\mu(p_{|\rho})\right\|_{2}\right]\geq\widetilde{\Omega}\left(\frac{\epsilon}{m^{8.5}\sqrt{n}}\right).$
(9)

This is handled in the first for-loop of the main case, where
ProjectedTestMean is used as a subroutine to tell whether $p_{|\rho}$ is
uniform or has a bias vector with a large $\ell_{2}$-norm. (Note that subcube
conditional query access to $p$ is used to simulate sample access to
$p_{|\rho}$ needed by ProjectedTestMean.) The parameter $L$ used in this for-
loop is defined as the inverse of the RHS of (9) so $L$ satisfies

$L:=L(n,\epsilon)=\widetilde{O}\left(\frac{m^{8.5}\sqrt{n}}{\epsilon}\right).$
(10)

For the other case when
$\mathbb{E}_{\rho\sim\mathcal{D}_{\sigma}(p)}[d_{TV}(p_{|\rho},\mathcal{U})]\geq\epsilon/2$,
note that a typical draw of $\rho\sim\mathcal{D}_{\rho}(p)$ satisfies both
that $d_{TV}(p_{|\rho},\mathcal{U})$ remains large and that the dimension
$|\text{stars}(\rho)|$ of $p_{|\rho}$ is much smaller (i.e., $\approx\sigma
n$). Intuitively this case is handled using recursive calls to SubCondUni in
the second for-loop. (Note that subcube conditional query access to $p$ can be
used to simulate subcube conditional query access to $p_{|\rho}$ needed by
recursive calls to SubCondUni.)

The proof of Theorem 1 using SubCondUni follows similar arguments used in the
proof of Theorem 2.1 of [CCK+21]. We included the proof in Appendix A for
completeness.

##  3 Robust Pisier’s Inequality on Hypergrids

In this section, we prove a robust version of Pisier’s inequality on functions
over hypergrids $\mathbb{Z}_{m_{1}}\times\dots\times\mathbb{Z}_{m_{n}}$, for
$m_{1},\dots,m_{n}\geq 2$. This inequality will play a crucial role in the
proof of the main technical lemma, Lemma 9. First, let $\mathbb{Z}_{M}$ denote
$\mathbb{Z}_{m_{1}}\times\dots\times\mathbb{Z}_{m_{n}}$, where
$M=(m_{1},\dots,m_{n})$.

Our notion of robustness is similar to that of [CCK+21] and [KMS18], where the
inequality holds for any orientation of an undirected graph $\mathcal{H}$ over
$\mathbb{Z}_{M}$, which will be defined below.

Given $x\in\mathbb{Z}_{M}$, $i\in[n]$ and $a\in\mathbb{Z}_{m_{i}}$, we write
$x^{(i)\to a}$ to denote the vector that satisfies $x^{(i)\to a}_{j}=x_{j}$
for all $j\neq i$, and $\smash{x^{(i)\to a}_{i}}=a$. Let $\mathcal{H}$ be the
undirected graph over $\mathbb{Z}_{M}$ that consists of undirected edges
$\\{x,x^{(i)\to a}\\}$ for all $x\in\mathbb{Z}_{M}$, $i\in[n]$, and
$a\in\mathbb{Z}_{m_{i}}$ such that $x_{i}\neq a$. (Equivalently, $\\{x,y\\}$
is an undirected edge in $\mathcal{H}$ if there exists an $i\in[n]$ such that
$x_{i}\neq y_{i}$ and $x_{j}=y_{j}$ for all $j\neq i$.)

Consider a function $f:\mathbb{Z}_{M}\rightarrow\mathbb{C}$, we recall the
definition of the Laplacian operator $L_{i}f$ ([O’D21]):

######  Definition 10.

Let $i\in[n]$ and $f:\mathbb{Z}_{M}\to\mathbb{C}$. The ith coordinate
Laplacian operator $L_{i}f$ is defined by:

$L_{i}f(x)=f(x)-\mathbb{E}_{a\sim\mathbb{Z}_{m_{i}}}\big{[}f(x^{(i)\rightarrow
a})\big{]}.$

Given $a\in\mathbb{Z}_{m_{i}}$, we define $L_{i}^{a}f$ to be

$L_{i}^{a}f(x)=\frac{f(x)-f(x^{(i)\to a})}{m_{i}}.$

So we have $L_{i}f(x)=\sum_{a\in\mathbb{Z}_{m_{i}}}L_{i}^{a}f(x)$.

For each $j\in[n]$, let $\mathbb{Z}_{m_{j}}^{*}=\\{1,\ldots,m_{j}-1\\}$ and
let $\omega_{j}=e^{2\pi i/m_{j}}$ be the primitive $m_{j}$-th root of unity.
We are now ready to state our robust Pisier’s inequality for functions over
$\mathbb{Z}_{M}$:

######  Theorem 11 (Robust Pisier’s Inequality for Functions over
$\mathbb{Z}_{M}$).

Let $f:\mathbb{Z}_{M}\to\mathbb{C}$ be a function with
$\mathbb{E}_{x\sim\mathbb{Z}_{M}}[f(x)]=0$ and let $G$ be an orientation of
$\mathcal{H}$. Then for any $s\in[1,\infty)$ we have

$\displaystyle\Big{(}\mathbb{E}_{x\sim\mathbb{Z}_{M}}\big{[}\left\lvert
f(x)\right\rvert^{s}\big{]}\Big{)}^{1/s}$ $\displaystyle\hskip
14.22636pt\lesssim\log(n)\cdot\left(\mathbb{E}_{x,y\sim\mathbb{Z}_{M}}\left[\left\lvert\sum_{i\in[n]}\sum_{a\in\mathbb{Z}_{m_{i}}^{*}}\sum_{\begin{subarray}{c}d\in\mathbb{Z}_{m_{i}}^{*}\\\
(x,x^{(i)\to x_{i}+d})\in
G\end{subarray}}(1-\omega_{i}^{ad})\omega_{i}^{-ay_{i}}\omega_{i}^{ax_{i}}L_{i}^{x_{i}+d}f(x)\right\rvert^{s}\right]\right)^{1/s}.$

###  3.1 Fourier Analysis over Hypergrids

Given $M=(m_{1},\ldots,m_{n})$, we will use Fourier analysis over
$\mathbb{Z}_{M}$ (see [CGS+21, O’D21]). To this end, we represent any function
$f:\mathbb{Z}_{M}\to\mathbb{C}$ using this Fourier basis with the following
expression:

$f(x)=\sum_{u\in\mathbb{Z}_{M}}\hat{f}(u)\cdot\prod_{i\in[n]}\omega_{i}^{u_{i}x_{i}},$

where the Fourier coefficients $\hat{f}(u)$ are given by

$\hat{f}(u)=\left(\prod_{i=1}^{n}\frac{1}{m_{i}}\right)\sum_{x\in\mathbb{Z}_{M}}f(x)\cdot{\prod_{i\in[n]}\omega_{i}^{-u_{i}x_{i}}}.$

We will use the following fact about the $i$th coordinate Laplacian operator:

$L_{i}f(x)=\sum_{u\in\mathbb{Z}_{M}:u_{i}\neq
0}\hat{f}(u)\cdot\prod_{i\in[n]}\omega_{i}^{u_{i}x_{i}}.$ (11)

Given $\rho\in[0,1]$ and $x\in\mathbb{Z}_{M}$, we write $N_{\rho}(x)$ to
denote the following distribution supported on $\mathbb{Z}_{M}$: To sample
$y\sim N_{\rho}(x)$, for each $i\in[n]$ we set $y_{i}=x_{i}$ with probability
$\rho$, and set $y_{i}$ to be a uniform random number from
$\mathbb{Z}_{m_{i}}$ with probability $1-\rho$.

######  Definition 12 (Noise Operator).

Given $f:\mathbb{Z}_{M}\rightarrow\mathbb{C}$ and $\rho\in[0,1]$, the noise
operator $T_{\rho}$ is defined as

$T_{\rho}f(x)=\mathbb{E}_{y\sim N_{\rho}(x)}\big{[}f(y)\big{]}.$

Given $u\in\mathbb{Z}_{M}$, we write

$\text{supp}(u)=\\{i\in[n]:u_{i}\neq
0\\}\quad\text{and}\quad\\#u=|\text{supp}(u)|.$

The following proposition relates the noise operator to its Fourier expansion.
The proposition can be found in [O’D21] for the case of $m_{1}=\dots=m_{n}$.

######  Proposition 13.

Let $\rho\in[0,1]$ and let $f:\mathbb{Z}_{M}\to\mathbb{C}$. Then, the Fourier
expansion of $T_{\rho}f$ is given by:

$T_{\rho}f(x)=\sum_{u\in\mathbb{Z}_{M}}\rho^{(\\#u)}\hat{f}(u)\cdot\prod_{i\in[n]}\omega_{i}^{u_{i}x_{i}}.$

###### Proof.

By the definition of $T_{\rho}$ we have

$T_{\rho}f(x)=\mathbb{E}_{y\sim
N_{\rho}(x)}\big{[}f(y)\big{]}=\sum_{u\in\mathbb{Z}_{M}}\hat{f}(u)\cdot\mathbb{E}_{y\sim
N_{\rho}(x)}\left[\prod_{i\in[n]}\omega_{i}^{u_{i}y_{i}}\right].$

Next, we have

$\mathbb{E}_{y\sim
N_{\rho}(x)}\left[\prod_{i\in[n]}\omega_{i}^{u_{i}y_{i}}\right]=\prod_{i\in[n]}\left(\rho\cdot\omega_{i}^{u_{i}x_{i}}+\frac{1-\rho}{m_{i}}\sum_{z\in\mathbb{Z}_{m_{i}}}\omega_{i}^{u_{i}z}\right)=\rho^{(\\#u)}\prod_{i\in[n]}\omega_{i}^{u_{i}x_{i}}.$

This is because if $u_{i}\neq 0$, then the sum of $\omega_{i}^{u_{i}z}$ is $0$
and the $i$-th coordinate contributes $\rho\cdot\omega_{i}^{u_{i}x_{i}}$ to
the product. If $u_{i}=0$, the $i$-th coordinate contributes
$\rho+1-\rho=1=\omega_{i}^{u_{i}x_{i}}$ to the product. ∎

Now, for any $x,y\in\mathbb{Z}_{M}$ and $t\in[0,1]$, consider the distribution
$N_{t,1-t}(x,y)$, supported on $\mathbb{Z}_{M}$, to be the distribution given
by letting $z\sim N_{t,1-t}(x,y)$ have each $i\in[n]$ set to $z_{i}=x_{i}$
with probability $t$ and $z_{i}=y_{i}$ otherwise. Given a function
$g:\mathbb{Z}_{M}\to\mathbb{C}$ and $t\in[0,1]$, we define

$g_{t,1-t}(x,y)=\mathbb{E}_{z\sim
N_{t,1-t}(x,y)}\big{[}g(z)\big{]}=\sum_{u\in\mathbb{Z}_{M}}\hat{g}(u)\prod_{i\in[n]}\Big{(}t\omega_{i}^{u_{i}x_{i}}+(1-t)\omega_{i}^{u_{i}y_{i}}\Big{)},$
(12)

where the second equation follows from arguments similar to the proof of
Proposition 13.

Lastly, for any $\gamma>0$, we let $\Delta^{\gamma}f$ be the operator given
by:

$\Delta^{\gamma}f(x)=\sum_{u\in\mathbb{Z}_{M}}\hat{f}(u)(\\#u)^{\gamma}\prod_{i\in[n]}\omega_{i}^{u_{i}x_{i}}.$
(13)

###  3.2 Proof of the Robust Pisier’s Inequality over Hypergrids

Our proof follows the proof of [NS02] (Theorem 2). For the robustness part, it
adapts the proof strategy of [CCK+21]. Let $M=\\{m_{1},\dots,m_{n}\\}$. We
start with the following lemma:

######  Lemma 14.

Let $f,g:\mathbb{Z}_{M}\to\mathbb{C}$ be two functions with
$\mathbb{E}_{x\sim\mathbb{Z}_{M}}[f(x)]=0$. Then we have

$\displaystyle\sum_{u\neq
0\in\mathbb{Z}_{M}}t^{(\\#u)-1}(\\#u)^{\gamma+1}\cdot\hat{f}(u)\overline{\hat{g}(u)}=\frac{1}{1-t}\cdot\mathbb{E}_{x,y\sim\mathbb{Z}_{M}}\left[\overline{g_{t,1-t}(x,y)}\cdot\sum_{i\in[n]}\sum_{a\in\mathbb{Z}_{m_{i}}^{*}}\omega_{i}^{-ay_{i}}\omega_{i}^{ax_{i}}L_{i}\Delta^{\gamma}f(x)\right].$

###### Proof.

We work on the sum

$\overline{g_{t,1-t}(x,y)}\cdot\sum_{i\in[n]}\sum_{a\in\mathbb{Z}_{m_{i}}^{*}}\omega_{i}^{-ay_{i}}\omega_{i}^{ax_{i}}L_{i}\Delta^{\gamma}f(x).$
(14)

Replacing $g_{t,1-t}(x,y)$ using the RHS of (12) and
$L_{i}\Delta^{\gamma}f(x)$ using (11) and (13), (14) becomes

$\left[\sum_{v\in\mathbb{Z}_{M}}\overline{\hat{g}(v)}\prod_{j\in[n]}\big{(}t\omega_{j}^{-v_{j}x_{j}}+(1-t)\omega_{j}^{-v_{j}y_{j}}\big{)}\right]\left[\sum_{i\in[n]}\sum_{a\in\mathbb{Z}_{m_{i}}^{*}}\omega_{i}^{-ay_{i}}\omega_{i}^{ax_{i}}\sum_{u\in\mathbb{Z}_{M}:u_{i}\neq
0}(\\#u)^{\gamma}\hat{f}(u)\prod_{k\in[n]}\omega_{k}^{u_{k}x_{k}}\right].$
(15)

Next, upon expanding, (15) becomes:

$\sum_{i\in[n]}\sum_{u\in\mathbb{Z}_{M}:u_{i}\neq
0}\sum_{v\in\mathbb{Z}_{M}}\hat{f}(u)\overline{\hat{g}(v)}(\\#u)^{\gamma}\sum_{a\in\mathbb{Z}_{m_{i}}^{*}}\omega_{i}^{-ay_{i}}\omega_{i}^{ax_{i}}\left(\prod_{j\in[n]}\omega_{j}^{u_{j}x_{j}}\left(t\omega_{j}^{-v_{j}x_{j}}+(1-t)\omega_{j}^{-v_{j}y_{j}}\right)\right).$
(16)

Let us take the expectation of this expression over $x,y\sim\mathbb{Z}_{M}$.
By linearity of expectation, we get

$\displaystyle\sum_{i\in[n]}\sum_{u\in\mathbb{Z}_{M}:u_{i}\neq
0}\sum_{v\in\mathbb{Z}_{M}}\hat{f}(u)\overline{\hat{g}(v)}(\\#u)^{\gamma}\sum_{a\in\mathbb{Z}_{m_{i}}^{*}}A_{i,u,v,a}$
$\displaystyle\hskip
28.45274pt=\sum_{u\in\mathbb{Z}_{M}}\sum_{i\in[n]:u_{i}\neq
0}\sum_{v\in\mathbb{Z}_{M}}\hat{f}(u)\overline{\hat{g}(v)}(\\#u)^{\gamma}\sum_{a\in\mathbb{Z}_{m_{i}}^{*}}A_{i,u,v,a},$
(17)

where

$A_{i,u,v,a}:=\mathbb{E}_{x,y\sim\mathbb{Z}_{M}}\left[\omega_{i}^{-ay_{i}}\omega_{i}^{ax_{i}}\left(\prod_{j\in[n]}\omega_{j}^{u_{j}x_{j}}\left(t\omega_{j}^{-v_{j}x_{j}}+(1-t)\omega_{j}^{-v_{j}y_{j}}\right)\right)\right].$

Furthermore, $A_{i,u,v,a}$ can be written as a product of $n$ expectations.
The $i$th expectation is given by

$\mathbb{E}_{x_{i},y_{i}\sim\mathbb{Z}_{m_{i}}}\Big{[}\omega_{i}^{-ay_{i}}\omega_{i}^{ax_{i}}\omega_{i}^{u_{i}x_{i}}\left(t\omega_{i}^{-v_{i}x_{i}}+(1-t)\omega_{i}^{-v_{i}y_{i}}\right)\Big{]}.$

The $i$th expectation can be written as the expectation of a sum of two terms.
Given that $a\neq 0$, the expectation of the first term is always $0$. The
expectation of the second term is $(1-t)$ when $v_{i}=u_{i}=-a$, and is $0$
otherwise. Similarly, the $j$th expectation, for each $j\neq i$, is given by

$\mathbb{E}_{x_{j},y_{j}\sim\mathbb{Z}_{m_{j}}}\left[\omega_{j}^{u_{j}x_{j}}\left(t\omega_{j}^{-v_{j}x_{j}}+(1-t)\omega_{j}^{-v_{j}y_{j}}\right)\right],$

which is $0$ when $u_{j}\neq v_{j}$. When $u_{j}=v_{j}$, the expectation is
$t$ if $u_{j}=v_{j}\neq 0$ and is $1$ if $u_{j}=v_{j}=0$.

Given this analysis, we have that for any given $i$ and $u$ such that
$u_{i}\neq 0$, there is a unique choice for $a$ (i.e.,
$a=-u_{i}\in\mathbb{Z}_{m_{i}}^{*}$) and $v$ (i.e., $v=u$) such that
$A_{i,u,v,a}$ is nonzero and is equal to

$(1-t)\cdot t^{\text{number of $j\neq i$ such that $u_{j}\neq 0$}}=(1-t)\cdot
t^{(\\#u)-1}.$

As a result, (17) can be simplified to

$\sum_{u\in\mathbb{Z}_{M}}\sum_{i\in[n]:u_{i}\neq
0}\hat{f}(u)\overline{\hat{g}(u)}(\\#u)^{\gamma}\cdot({1-t})\cdot
t^{(\\#u)-1}=(1-t)\cdot\sum_{u\neq
0\in\mathbb{Z}_{M}}\hat{f}(u)\overline{\hat{g}(u)}(\\#u)^{\gamma+1}t^{(\\#u)-1},$

from which the lemma follows. ∎

Recall that given two functions $f,g:\mathbb{Z}_{M}\rightarrow\mathbb{C}$, we
write

$\|f\|_{s}:=\Big{(}\mathbb{E}_{x\sim\mathbb{Z}_{M}}\big{[}|f(x)|^{s}\big{]}\Big{)}^{1/s}\quad\text{and}\quad\langle
f,g\rangle:=\mathbb{E}_{x\sim\mathbb{Z}_{M}}\big{[}f(x)\overline{g(x)}\big{]}.$

We are now ready to prove Theorem 11:

###### Proof of Theorem 11.

Let $\rho=1-1/(n+1)$ and $q\in[1,\infty)$ such that
$\frac{1}{s}+\frac{1}{q}=1$. Given $f$, let $g:\mathbb{Z}_{M}\to\mathbb{C}$ be
a function with $\|g\|_{q}=1$ satisfying $\langle
T_{\rho}f,g\rangle=\|T_{\rho}f\|_{s}$. We have

$(2\rho-1)^{n}\cdot\|f\|_{s}\leq\|T_{\rho}f\|_{s}=\langle
T_{\rho}f,g\rangle=\sum_{u\neq
0\in\mathbb{Z}_{M}}\rho^{(\\#u)}\hat{f}(u)\overline{\hat{g}(u)},$

where the last equation used the assumption that $\hat{f}(0)=0.$ Let
$\gamma>0$ be a parameter, which will approach $0$ at the end of the proof. By
writing

$\rho^{(\\#u)}=\frac{1}{\Gamma(1+\gamma)}\int_{0}^{\rho}t^{(\\#u)-1}(\\#u)^{\gamma+1}\big{(}\log(\rho/t)\big{)}^{\gamma}dt,$

for every $u\neq 0$ (in which case $\\#u>0$), we have

$(2\rho-1)^{n}\cdot\|f\|_{s}\leq\frac{1}{\Gamma(1+\gamma)}\int_{0}^{\rho}\left(\sum_{u\neq
0\in\mathbb{Z}_{M}}t^{(\\#u)-1}(\\#u)^{\gamma+1}\hat{f}(u)\overline{\hat{g}(u)}\right)\big{(}\log(\rho/t)\big{)}^{\gamma}dt.$
(18)

By Lemma 14, the RHS of (18) is

$\frac{1}{\Gamma(1+\gamma)}\int_{0}^{\rho}\frac{1}{1-t}\cdot\mathbb{E}_{x,y\sim\mathbb{Z}_{M}}\left[\overline{g_{t,1-t}(x,y)}\sum_{i\in[n]}\sum_{a\in\mathbb{Z}_{m_{i}}^{*}}\omega_{i}^{-ay_{i}}\omega_{i}^{ax_{i}}L_{i}\Delta^{\gamma}f(x)\right]\cdot\big{(}\log(\rho/t)\big{)}^{\gamma}dt.$
(19)

Plugging in $L_{i}f(x)=\sum_{b\in\mathbb{Z}_{m_{i}}}L_{i}^{b}f(x)$, this
equals

$\frac{1}{\Gamma(1+\gamma)}\int_{0}^{\rho}\frac{1}{1-t}\cdot\mathbb{E}_{x,y\sim\mathbb{Z}_{M}}\left[\overline{g_{t,1-t}(x,y)}\sum_{i\in[n]}\sum_{a\in\mathbb{Z}_{m_{i}}^{*}}\sum_{b\in\mathbb{Z}_{m_{i}}}\omega_{i}^{-ay_{i}}\omega_{i}^{ax_{i}}L_{i}^{b}\Delta^{\gamma}f(x)\right]\cdot\big{(}\log(\rho/t)\big{)}^{\gamma}dt.$

Since this expression equals $||T_{\rho}f||_{s}$, which is real-valued, we can
say it is less than its absolute value:

$\leq\left\lvert\frac{1}{\Gamma(1+\gamma)}\int_{0}^{\rho}\frac{1}{1-t}\cdot\mathbb{E}_{x,y\sim\mathbb{Z}_{M}}\left[\overline{g_{t,1-t}(x,y)}\sum_{i\in[n]}\sum_{a\in\mathbb{Z}_{m_{i}}^{*}}\sum_{b\in\mathbb{Z}_{m_{i}}}\omega_{i}^{-ay_{i}}\omega_{i}^{ax_{i}}L_{i}^{b}\Delta^{\gamma}f(x)\right]\cdot\big{(}\log(\rho/t)\big{)}^{\gamma}dt\right\rvert$
$\leq\frac{1}{\Gamma(1+\gamma)}\int_{0}^{\rho}\frac{1}{1-t}\cdot\left\lvert\mathbb{E}_{x,y\sim\mathbb{Z}_{M}}\left[\overline{g_{t,1-t}(x,y)}\sum_{i\in[n]}\sum_{a\in\mathbb{Z}_{m_{i}}^{*}}\sum_{b\in\mathbb{Z}_{m_{i}}}\omega_{i}^{-ay_{i}}\omega_{i}^{ax_{i}}L_{i}^{b}\Delta^{\gamma}f(x)\right]\right\rvert\cdot\big{(}\log(\rho/t)\big{)}^{\gamma}dt.$

Our next step is to obtain the following:

$\displaystyle\left\lvert\mathbb{E}_{x,y\sim\mathbb{Z}_{M}}\left[\overline{g_{t,1-t}(x,y)}\sum_{i\in[n]}\sum_{a\in\mathbb{Z}_{m_{i}}^{*}}\sum_{b\in\mathbb{Z}_{m_{i}}}\omega_{i}^{-ay_{i}}\omega_{i}^{ax_{i}}L_{i}^{b}\Delta^{\gamma}f(x)\right]\right\rvert$
$\displaystyle\hskip
14.22636pt=\left\lvert\mathbb{E}_{x,y\sim\mathbb{Z}_{M}}\left[\overline{g_{t,1-t}(x,y)}\sum_{i\in[n]}\sum_{a\in\mathbb{Z}_{m_{i}}^{*}}\sum_{\begin{subarray}{c}d\in\mathbb{Z}_{m_{i}}^{*}\\\
(x,x^{(i)\to x_{i}+d})\in
G\end{subarray}}\omega_{i}^{-ay_{i}}\omega_{i}^{ax_{i}}L_{i}^{x_{i}+d}\Delta^{\gamma}f(x)\cdot\left(1-\omega_{i}^{ad}\right)\right]\right\rvert$
(20) $\displaystyle\hskip
14.22636pt\leq\left(\mathbb{E}_{x,y\sim\mathbb{Z}_{M}}\left[\left\lvert\sum_{i\in[n]}\sum_{a\in\mathbb{Z}_{m_{i}}^{*}}\sum_{\begin{subarray}{c}d\in\mathbb{Z}_{m_{i}}^{*}\\\
(x,x^{(i)\to x_{i}+d})\in
G\end{subarray}}(1-\omega_{i}^{ad})\omega_{i}^{-ay_{i}}\omega_{i}^{ax_{i}}L_{i}^{x_{i}+d}\Delta^{\gamma}f(x)\right\rvert^{s}\right]\right)^{1/s}.$
(21)

To prove (20) we note that $L_{i}^{a}\Delta^{\gamma}f(x^{(i)\to
a+d})=-L_{i}^{a+d}\Delta^{\gamma}f(x^{(i)\to a})$. This is because

$L_{i}^{a}\Delta^{\gamma}f(x^{(i)\to
a+d})=\frac{\Delta^{\gamma}f(x^{(i)\rightarrow
a+d})-\Delta^{\gamma}f(x^{(i)\rightarrow
a})}{m_{i}}=-L_{i}^{a+d}\Delta^{\gamma}f(x^{(i)\rightarrow a}).$

In the summation, we group terms corresponding to edges of $\mathcal{H}$
according to the orientation $G$:

$\displaystyle\mathbb{E}_{x,y\sim\mathbb{Z}_{M}}\left[\overline{g_{t,1-t}(x,y)}\sum_{i\in[n]}\sum_{a\in\mathbb{Z}_{m_{i}}^{*}}\sum_{b\in\mathbb{Z}_{m_{i}}}\omega_{i}^{-ay_{i}}\omega_{i}^{ax_{i}}L_{i}^{b}\Delta^{\gamma}f(x)\right]$
$\displaystyle=\mathbb{E}_{x\sim\mathbb{Z}_{M}}\Bigg{[}\sum_{i\in[n]}\sum_{a\in\mathbb{Z}_{m_{i}}^{*}}\sum_{\begin{subarray}{c}d\in\mathbb{Z}_{m_{i}}^{*}\\\
(x,x^{(i)\to x_{i}+d})\in
G\end{subarray}}\mathbb{E}_{y\sim\mathbb{Z}_{M}}\bigg{[}\overline{g_{t,1-t}(x,y)}\cdot\omega_{i}^{-ay_{i}}\omega_{i}^{ax_{i}}L_{i}^{x_{i}+d}\Delta^{\gamma}f(x)$
$\displaystyle\hskip 113.81102pt+\overline{g_{t,1-t}(x^{(i)\to
x_{i}+d},y)}\cdot\omega_{i}^{-ay_{i}}\omega_{i}^{a(x_{i}+d)}L_{i}^{x_{i}}\Delta^{\gamma}f(x^{(i)\to
x_{i}+d})\bigg{]}\Bigg{]}$
$\displaystyle=\mathbb{E}_{x\sim\mathbb{Z}_{M}}\Bigg{[}\sum_{i\in[n]}\sum_{a\in\mathbb{Z}_{m_{i}}^{*}}\sum_{\begin{subarray}{c}d\in\mathbb{Z}_{m_{i}}^{*}\\\
(x,x^{(i)\to x_{i}+d})\in
G\end{subarray}}\mathbb{E}_{y\sim\mathbb{Z}_{M}}\bigg{[}\overline{g_{t,1-t}(x,y)}\cdot\omega_{i}^{-ay_{i}}\omega_{i}^{ax_{i}}L_{i}^{x_{i}+d}\Delta^{\gamma}f(x)$
$\displaystyle\hskip 113.81102pt-\overline{g_{t,1-t}(x^{(i)\to
x_{i}+d},y)}\cdot\omega_{i}^{-ay_{i}}\omega_{i}^{a(x_{i}+d)}L_{i}^{x_{i}+d}\Delta^{\gamma}f(x)\bigg{]}\Bigg{]}.$
(22)

Next, for a fixed $x$, $i$, $a$ and $d$, we have the following:

$\displaystyle\mathbb{E}_{y\sim\mathbb{Z}_{M}}\left[\overline{g_{t,1-t}(x,y)}\cdot\omega_{i}^{-ay_{i}}\omega_{i}^{ax_{i}}L_{i}^{x_{i}+d}\Delta^{\gamma}f(x)-\overline{g_{t,1-t}(x^{(i)\to
x_{i}+d},y)}\cdot\omega_{i}^{-ay_{i}}\omega_{i}^{a(x_{i}+d)}L_{i}^{x_{i}+d}\Delta^{\gamma}f(x)\right]$
$\displaystyle\hskip
17.07182pt=(1-\omega_{i}^{ad})\cdot\mathbb{E}_{y\sim\mathbb{Z}_{M}}\left[\overline{g_{t,1-t}(x,y)}\cdot\omega_{i}^{-ay_{i}}\omega_{i}^{ax_{i}}L_{i}^{x_{i}+d}\Delta^{\gamma}f(x)\right].$
(23)

This equation follows because when expanding the terms in

$\overline{g_{t,1-t}(x,y)}=\mathbb{E}_{z\sim
N_{t,1-t}(x,y)}\Big{[}\overline{g(z)}\Big{]}\quad\text{and}\quad\overline{g_{t,1-t}(x^{(i)\rightarrow
x_{i}+d},y)}={\mathbb{E}_{z^{\prime}\sim N_{t,1-t}(x^{(i)\to
x_{i}+d},y)}\Big{[}\overline{g(z^{\prime})}\Big{]}},$

the LHS of (23) becomes

$\mathbb{E}_{y\sim\mathbb{Z}_{M},z,z^{\prime}}\Big{[}\overline{g(z)}\cdot\omega_{i}^{-ay_{i}}\omega_{i}^{ax_{i}}L_{i}^{x_{i}+d}\Delta^{\gamma}f(x)-\overline{g(z^{\prime})}\cdot\omega_{i}^{-ay_{i}}\omega_{i}^{a(x_{i}+d)}L_{i}^{x_{i}+d}\Delta^{\gamma}f(x)\Big{]},$

where $z$ and $z^{\prime}$ are drawn using the natural coupling that $z\sim
N_{t,1-t}(x,y)$ and $z^{\prime}$ is set to be $z$ if $z_{i}=y_{i}$ and
$z^{\prime}$ is set to be $z^{(i)\rightarrow x_{i}+d}$ if $z_{i}=x_{i}$.
Consider the following two cases:

  1. 1.

Either $z_{i}=y_{i}$ in which case $z^{\prime}=z$ and thus, the contribution
of the second term is always the contribution of the first term scaled by
$-\omega_{i}^{ad}$;

  2. 2.

Or, $z_{i}=x_{i}$. In this case, both terms are independent of $y_{i}$ and
thus, have an overall contribution of zero, as
$\mathbb{E}_{y_{i}\sim\mathbb{Z}_{m_{i}}}[\omega_{i}^{-ay_{i}}]=0$ given that
$a\neq 0$.

This finishes the proof of (20).

To obtain (21) from (20), we note that
$\|\overline{g_{t,1-t}}\|_{q}\leq\|g\|_{q}=1$ and apply Hölder’s inequality.

We proceed by substituting (21) into (18). For $\rho=1-{1}/{(n+1)}$, we have
when $\gamma$ approaches $0$,

$\frac{1}{\Gamma(1+\gamma)}\int_{0}^{\rho}\frac{\log(\rho/t)^{\gamma}}{1-t}dt\lesssim\log
n.$

So we obtain:

$(2\rho-1)^{n}\|f\|_{s}\lesssim\log
n\cdot\left(\mathbb{E}_{x,y\sim\mathbb{Z}_{M}}\left[\left\lvert\sum_{i\in[n]}\sum_{a\in\mathbb{Z}_{m_{i}}^{*}}\sum_{\begin{subarray}{c}d\in\mathbb{Z}_{m_{i}}^{*}\\\
(x,x^{(i)\to x_{i}+d})\in
G\end{subarray}}(1-\omega_{i}^{ad})\omega_{i}^{-ay_{i}}\omega_{i}^{ax_{i}}L_{i}^{x_{i}+d}\Delta^{\gamma}f(x)\right\rvert^{s}\right]\right)^{1/s}$

As $\gamma\to 0$, the RHS approaches the desired quantity, while the LHS is
independent of $\gamma$. ∎

##  4 Proof of Lemma 9

We prove Lemma 9 in this section. We follow the high-level strategy used in
Section 3 of [CCK+21] but need to overcome a number of obstacles that are
unique to hypergrids.

Let $t\in[n-1]$ be the parameter from Lemma 9. For this section, let $T$
denote a subset of $[n]$ of size $t$, and let $S$ denote a subset of $[n]$ of
size $t+1$.

The steps of the proof of Lemma 9 are as follows. First, we apply the robust
Pisier’s inequality over hypergrids to connect the total variation distance
$d_{TV}(p_{\overline{T}},\mathcal{U})$, for a given $t$-subset $T$ of $[n]$,
to the average $\sqrt{\text{outdegree}}$ of a collection of directed graphs
over $\mathbb{Z}_{K}$, where $K:=M_{\overline{T}}=(m_{i}:i\notin T)$ defines a
hypergrid $\mathbb{Z}_{K}$ of dimension $k:=n-t$. Next we connect these graphs
with the bias vector $\mu(p_{|\rho})$ of either $\rho\sim\mathcal{D}(t,p)$ or
$\rho\sim\mathcal{D}(t+1,p)$ to finish the proof.

###  4.1 Connecting Total Variation Distance to Directed Graphs

Fix any $t$-subset $T$ of $[n]$ and let $K=M_{\overline{T}}$ of length
$k=n-t$. Let $\ell$ be a probability distribution over $\mathbb{Z}_{K}$.
(Later on in the proof of Lemma 9, we will let $\ell$ be $p_{\overline{T}}$.
We refer to $p_{\overline{T}}$ as $\ell$ in this subsection for notational
convenience.) Recall that $m=\max_{i\in[n]}m_{i}$ and thus,
$m\geq\max_{i\in\overline{T}}m_{i}$.

Let $\mathcal{H}$ denote the undirected graph over $\mathbb{Z}_{K}$ consisting
of undirected edges $\\{x,x^{(i)\to b}\\}$, for each $x\in\mathbb{Z}_{K}$,
$i\in\overline{T}$, and $b\in\mathbb{Z}_{m_{i}}$ with $b\neq x_{i}$. Next, we
assign weights to edges of $\mathcal{H}$ as follows.

######  Definition 15.

An undirected edge $\\{x,x^{(i)\to b}\\}\in\mathcal{H}$ is a zero edge if
$\ell(x)=\ell(x^{(i)\to b})$. For each nonzero edge $\\{x,x^{(i)\to
b}\\}\in\mathcal{H}$, let its weight be defined as:

$w(\\{x,x^{(i)\to b}\\}):=\frac{|\ell(x)-\ell(x^{(i)\to
b})|}{\max\\{\ell(x),\ell(x^{(i)\to b})\\}}.$

The weight of a nonzero edge is always in $(0,1]$. A nonzero edge is called
uneven if its weight is at least ${m}/({m+1})$. Otherwise (any nonzero edge
with weight smaller than ${m}/({m+1})$), we say it is an even edge. An even
edge is at scale $\kappa$ for some integer $\kappa\geq 1$ if:

$m^{-\kappa}<w\left(\\{x,x^{(i)\to b}\\}\right)\leq m^{-\kappa+1}.$

We partition edges of $\mathcal{H}$ to define three undirected graphs
$\mathcal{H}^{[z]},\mathcal{H}^{[u]},\mathcal{H}^{[e]}$ according to their
weights:

  1. 1.

$\mathcal{H}^{[u]}$ (where $u$ stands for “uneven”): Add all uneven edges of
$\mathcal{H}$ to $\mathcal{H}^{[u]}$.

  2. 2.

$\mathcal{H}^{[z]}$ (where $z$ stands for “zero”): Add all zero edges of
$\mathcal{H}$ to $\mathcal{H}^{[z]}$; and

  3. 3.

$\mathcal{H}^{[e]}$ (where $e$ stands for “even”): Add all even edges of
$\mathcal{H}$ to $\mathcal{H}^{[e]}$.

Next we assign orientations to edges in $\mathcal{H}^{[u]}$ and
$\mathcal{H}^{[z]}$ to obtain directed graphs $G^{[u]}$ and $G^{[z]}$:

  1. 1.

$G^{[u]}$: For each uneven edge $\\{x,y\\}\in\mathcal{H}^{[u]}$, orient the
edge from $x$ to $y$ if $\ell(x)>\ell(y)$ and from $y$ to $x$ if
$\ell(y)>\ell(x)$. Note that $\ell(x)\neq\ell(y)$ since it is not a zero edge
so the directions are well defined.

  2. 2.

$G^{[z]}$: Orient each zero edge $\\{x,y\\}\in\mathcal{H}^{[z]}$ arbitrarily.

Orientations of even edges are trickier. Notably our construction below is
significantly different from that of [CCK+21]. We partition and orient even
edges into directed graphs $G^{[\kappa]}$ for each $\kappa\geq 1$ and
$G^{[r]}$, where each $G^{[\kappa]}$ contains orientations of a subset of even
edges at scale $\kappa$ and $G^{[r]}$ (where $r$ stands for “remaining”)
contains orientations of even edges not included in $G^{[\kappa]}$’s:

  1. 1.

$G^{[\kappa]}$, for each $\kappa\geq 1$: First we define
$\mathcal{H}^{[\kappa]}$ to be the undirected graph over $\mathbb{Z}_{K}$ that
includes all even edges $\\{x,y\\}\in\mathcal{H}$ of scale $\kappa$ if
$y=x^{(i)\to b}$ for some $i$ and $b$ (so the edge is along the $i$-th
direction) satisfies that _neither $x$ nor $y$ has any outgoing edges in
$G^{[u]}$ along the $i$-th direction_.

We then orient edges in $\mathcal{H}^{[\kappa]}$ to obtain the directed graph
$G^{[\kappa]}$ as follows. For each $\kappa\geq 1$, find an ordering of
vertices in $\mathbb{Z}_{K}$ as a bijection
$\smash{\rho_{\kappa}:\mathbb{Z}_{K}\to[\prod_{j\in\overline{T}}m_{j}]}$
(i.e., $x$ is the $\rho_{\kappa}(x)$-th vertex in the ordering) such that
$\rho_{\kappa}$ satisfies the following property: For each
$i\in[\prod_{j\in\overline{T}}m_{j}-1]$, the degree of
$\smash{\rho_{\kappa}^{-1}(i)}$ is the largest out of all vertices in the
subgraph of $\smash{\mathcal{H}^{[\kappa]}}$ induced by
$\smash{\\{\rho_{\kappa}^{-1}(j):j\geq i\\}}$.

Starting with $i=1$, one can construct such a bijection $\rho_{\kappa}$ by
deleting vertices one at a time from $\smash{\mathcal{H}^{[\kappa]}}$, at each
step deleting the vertex with the largest degree in the remaining undirected
graph, making it $\rho_{\kappa}(i)$ and setting $j=j+1$. Ties can be broken
arbitrarily.

We now use $\rho_{\kappa}$ to orient the edges in $\mathcal{H}^{[\kappa]}$ to
obtain the directed graph $G^{[\kappa]}$: For each undirected edge $\\{x,y\\}$
in $\mathcal{H}^{[\kappa]}$, orient the edge from $x$ to $y$ if
$\rho_{\kappa}(x)<\rho_{\kappa}(y)$, and orient the edge from $y$ to $x$
otherwise. This ensures that every directed edge $(x,y)\in G^{[\kappa]}$
satisfies $\rho_{\kappa}(x)<\rho_{\kappa}(y)$.

  2. 2.

$G^{[r]}$: For every even edge $\\{x,y\\}$ in $\mathcal{H}$ that was not
included in $\mathcal{H}^{[\kappa]}$’s (which means that one of its vertices
has at least one outgoing edge in $G^{[u]}$ along the same direction), add
$(x,y)$ to $G^{[r]}$ if $x$ has at least one outgoing edge in $G^{[u]}$ along
the same direction and add $(y,x)$ to $G^{[r]}$ if $y$ has at least one
outgoing edge along the same direction, breaking ties arbitrarily.

In the analysis proving Lemma 9, we will utilize the following fact about the
directed graph $G^{[\kappa]}$ (this fact, over hypercubes, can be found in
[CCK+21]):

######  Lemma 16.

Let $U$ be a set of vertices in $\mathbb{Z}_{K}$ and let
$v\in\mathbb{Z}_{K}\setminus U$. If the outdegree of every vertex $u\in U$ in
$G^{[\kappa]}$ is bounded from above by a positive integer $g$, then the
number of directed edges $(u,v)$ from a vertex $u\in U$ to $v$ in
$G^{[\kappa]}$ is also at most $g$.

###### Proof.

Consider the vertex $s$ that is ranked the highest (i.e., smallest value) in
$\rho_{\kappa}$ among $U\cup\\{v\\}$. If $s$ is $v$, then all undirected edges
between $U$ and $v$ are oriented from $v$ to $U$ so the number of directed
edges $(u,v)$ is $0$. If $s\in U$, then the assumption implies that the
subgraph of $\mathcal{H}^{[\kappa]}$ induced by $U\cup\\{v\\}$ has maximum
degree at most $g$, including the degree of $v$, from which the lemma follows
trivially. ∎

With $G^{[z]},G^{[u]}$, $G^{[\kappa]}$ for each $\kappa\geq 1$, and $G^{[r]}$
defined, we then define $G$ to be the union of these directed graphs, which is
an orientation of $\mathcal{H}$ over $\mathbb{Z}_{K}$.

We now apply Theorem 11 (the robust Pisier’s Inequality over hypergrids) in a
way that connects $d_{TV}(\ell,\mathcal{U})$ to the directed edges of $G$. To
do so, define the function $f:\mathbb{Z}_{K}\to[-1,\infty)$ as follows: For
each $y\in\mathbb{Z}_{K}$,

$f(y)=\left(\prod_{j\in\overline{T}}m_{j}\right)\cdot\ell(y)-1.$ (24)

Note that $\mathbb{E}_{y\sim\mathbb{Z}_{K}}[f(y)]=0$. Setting $s=1$, the left-
hand side of the robust Pisier’s inequality gives

$\mathbb{E}_{y\sim\mathbb{Z}_{K}}\big{[}\left\lvert
f(y)\right\rvert\big{]}=2\cdot d_{TV}(\ell,\mathcal{U}).$

We use the robust Pisier’s inequality to prove the following lemma:

######  Lemma 17.

For any probability distribution $\ell$ over $\mathbb{Z}_{K}$, we have

$\frac{d_{TV}(\ell,\mathcal{U})}{m^{1.5}\log^{2}n}\lesssim\mathbb{E}_{x\sim\mathbb{Z}_{K}}\left[\sqrt{\sum_{i\in\overline{T}}\sum_{\begin{subarray}{c}b\in\mathbb{Z}_{m_{i}}\\\
(x,x^{(i)\to b})\in G\end{subarray}}\left(L_{i}^{b}f(x)\right)^{2}}\right].$

###### Proof.

A direct application of the robust Pisier’s inequality (Theorem 11) with $s=1$
gives

$\frac{d_{TV}(\ell,\mathcal{U})}{\log
n}\lesssim\mathbb{E}_{x,y\sim\mathbb{Z}_{K}}\left[\left\lvert\sum_{i\in\overline{T}}\sum_{a\in\mathbb{Z}_{m_{i}}^{*}}\sum_{\begin{subarray}{c}d\in\mathbb{Z}_{m_{i}}^{*}\\\
(x,x^{(i)\to x_{i}+d})\in
G\end{subarray}}(1-\omega_{i}^{ad})\omega_{i}^{-ay_{i}}\omega_{i}^{ax_{i}}L_{i}^{x_{i}+d}f(x)\right\rvert\right]$

For convenience, we write $B_{x,i,a,d}$ to denote

$B_{x,i,a,d}:=(1-\omega_{i}^{ad})\omega_{i}^{ax_{i}}L_{i}^{x_{i}+d}f(x).$

Then the RHS of the inequality above becomes

$\mathbb{E}_{x,y\sim\mathbb{Z}_{K}}\left[\left\lvert\sum_{i\in\overline{T}}\sum_{a\in\mathbb{Z}_{m_{i}}^{*}}\sum_{\begin{subarray}{c}d\in\mathbb{Z}_{m_{i}}^{*}\\\
(x,x^{(i)\to x_{i}+d})\in
G\end{subarray}}\omega_{i}^{-ay_{i}}B_{x,i,a,d}\right\rvert\right].$ (25)

Let $R(z)$ and $I(z)$ denote the real and imaginary parts of a complex number
$z\in\mathbb{C}$. Then we have

$\displaystyle\left\lvert\sum_{i\in\overline{T}}\sum_{a\in\mathbb{Z}_{m_{i}}^{*}}\sum_{\begin{subarray}{c}d\in\mathbb{Z}_{m_{i}}^{*}\\\
(x,x^{(i)\to x_{i}+d})\in
G\end{subarray}}\omega_{i}^{-ay_{i}}B_{x,i,a,d}\right\rvert$
$\displaystyle\hskip
5.69046pt\leq\left\lvert\sum_{i\in\overline{T}}\sum_{a\in\mathbb{Z}_{m_{i}}^{*}}\sum_{\begin{subarray}{c}d\in\mathbb{Z}_{m_{i}}^{*}\\\
(x,x^{(i)\to x_{i}+d})\in
G\end{subarray}}R(\omega_{i}^{-ay_{i}})R(B_{x,i,a,d})\right\rvert+\left\lvert\sum_{i\in\overline{T}}\sum_{a\in\mathbb{Z}_{m_{i}}^{*}}\sum_{\begin{subarray}{c}d\in\mathbb{Z}_{m_{i}}^{*}\\\
(x,x^{(i)\to x_{i}+d})\in
G\end{subarray}}R(\omega_{i}^{-ay_{i}})I(B_{x,i,a,d})\right\rvert$
$\displaystyle\hskip
22.76228pt+\left\lvert\sum_{i\in\overline{T}}\sum_{a\in\mathbb{Z}_{m_{i}}^{*}}\sum_{\begin{subarray}{c}d\in\mathbb{Z}_{m_{i}}^{*}\\\
(x,x^{(i)\to x_{i}+d})\in
G\end{subarray}}I(\omega_{i}^{-ay_{i}})R(B_{x,i,a,d})\right\rvert+\left\lvert\sum_{i\in\overline{T}}\sum_{a\in\mathbb{Z}_{m_{i}}^{*}}\sum_{\begin{subarray}{c}d\in\mathbb{Z}_{m_{i}}^{*}\\\
(x,x^{(i)\to x_{i}+d})\in
G\end{subarray}}I(\omega_{i}^{-ay_{i}})I(B_{x,i,a,d})\right\rvert$

and we can now analyze real-valued random variables. We analyze the first of
the four terms:

$\mathbb{E}_{y\sim\mathbb{Z}_{K}}\left[\left\lvert\sum_{i\in\overline{T}}\sum_{a\in\mathbb{Z}_{m_{i}}^{*}}\sum_{\begin{subarray}{c}d\in\mathbb{Z}_{m_{i}}^{*}\\\
(x,x^{(i)\to x_{i}+d})\in
G\end{subarray}}R(\omega_{i}^{-ay_{i}})R(B_{x,i,a,d})\right\rvert\right],$
(26)

noting that the same analysis will apply to each of the other terms. Define
the random variable

$X_{i}=R(\omega^{-ay_{i}})\sum_{a\in\mathbb{Z}_{m_{i}}^{*}}\sum_{\begin{subarray}{c}d\in\mathbb{Z}_{m_{i}}^{*}\\\
(x,x^{(i)\to x_{i}+d})\in G\end{subarray}}R(B_{x,i,a,d})$

and note that the expectation of $X_{i}$ is $0$ over $y\sim\mathbb{Z}_{K}$.
Let

$\displaystyle t$ $\displaystyle:=100\log
n\cdot\sqrt{\sum_{i\in\overline{T}}\left(\sum_{a\in\mathbb{Z}_{m_{i}}^{*}}\sum_{\begin{subarray}{c}d\in\mathbb{Z}_{m_{i}}^{*}\\\
(x,x^{(i)\to x_{i}+d})\in G\end{subarray}}R(B_{x,i,a,d})\right)^{2}}$
$\displaystyle\leq O(\log
n)\cdot\sqrt{\sum_{i\in\overline{T}}m^{2}\sum_{a\in\mathbb{Z}^{*}_{m_{i}}}\sum_{\begin{subarray}{c}d\in\mathbb{Z}_{m_{i}}^{*}\\\
(x,x^{(i)\rightarrow x_{i}+d})\end{subarray}\in
G}\big{(}R(B_{x,i,a,d})\big{)}^{2}}$ $\displaystyle\leq O(m^{1.5}\log
n)\cdot\sqrt{\sum_{i\in\overline{T}}\sum_{\begin{subarray}{c}b\in\mathbb{Z}^{*}_{m_{i}}\\\
(x,x^{(i)\rightarrow b)}\in G\end{subarray}}\left(L_{i}^{b}f(x)\right)^{2}}.$

Bernstein’s inequality gives us that

$\mathbb{P}_{y\sim\mathbb{Z}_{K}}\left(\left\lvert\sum_{i\in\overline{T}}\sum_{a\in\mathbb{Z}_{m_{i}}^{*}}\sum_{\begin{subarray}{c}d\in\mathbb{Z}_{m_{i}}^{*}\\\
(x,x^{(i)\to x_{i}+d})\in
G\end{subarray}}R(\omega^{-ay_{i}})R(B_{x,i,a,d})\right\rvert\geq
t\right)\leq\frac{1}{n^{10}}.$

As a result, we know that (26) is at most

$\left(1-\frac{1}{n^{10}}\right)\cdot t+\frac{1}{n^{10}}\cdot nt<2t.$ (27)

The same series of steps applies to the other three terms and the lemma
follows. ∎

Letting $G^{\prime}$ be the directed graph that contains the union of edges in
$G^{[u]},G^{[r]}$ and $G^{[\kappa]}$, $\kappa\geq 1$, but not those in
$G^{[z]}$, we can replace the RHS of the Lemma 17 inequality with

$\mathbb{E}_{x\sim\mathbb{Z}_{K}}\left[\sqrt{\sum_{i\in\overline{T}}\sum_{\begin{subarray}{c}b\in\mathbb{Z}_{m_{i}}\\\
(x,x^{(i)\to b})\in
G\end{subarray}}\big{(}L_{i}^{b}f(x)\big{)}^{2}}\right]=\mathbb{E}_{x\sim\ell}\left[\sqrt{\sum_{i\in\overline{T}}\sum_{\begin{subarray}{c}b\in\mathbb{Z}_{m_{i}}\\\
(x,x^{(i)\to b})\in
G^{\prime}\end{subarray}}\left(\frac{L_{i}^{b}\ell(x)}{\ell(x)}\right)^{2}}\right].$

The next lemma connects the quantity in the expectation to the outdegree of
$x$ in $G^{[u]}$ and $G^{[\kappa]}$.

######  Lemma 18.

For every $x\in\mathbb{Z}_{K}$, we have

$\sum_{i\in\overline{T}}\sum_{\begin{subarray}{c}b\in\mathbb{Z}_{m_{i}}\\\
(x,x^{(i)\to b})\in
G^{\prime}\end{subarray}}\left(\frac{\ell(x)-\ell(x^{(i)\to
b})}{\ell(x)}\right)^{2}\leq
m^{3}\cdot\text{outdeg}(x,G^{[u]})+\sum_{\kappa\geq
1}4m^{-2\kappa+4}\cdot\text{outdeg}(x,G^{[\kappa]}).$

###### Proof.

Each edge $(x,x^{(i)\to b})\in G^{\prime}$ lies in $G^{[u]},G^{[r]}$ or
$G^{[\kappa]}$ for some $\kappa\geq 1$. If $(x,x^{(i)\to b})$ is in $G^{[u]}$,
then by the orientation of edges in $G^{[u]}$, we have $\ell(x)>\ell(x^{(i)\to
b})$, which implies that the contribution of each such edge to the sum on the
LHS is at most $1$.

Next, for each $(x,x^{(i)\to b})$ is in $G^{[\kappa]}$ for some $\kappa\geq
1$, since it is even, we have $\ell(x),\ell(x^{(i)\to b})>0$, since otherwise
it is a zero edge or uneven edge. Since $w(\\{x,x^{(i)\to b}\\})<{m}/({m+1})$,
we have:

$\frac{\max\\{\ell(x),\ell(x^{(i)\to b})\\}}{\min\\{\ell(x),\ell(x^{(i)\to
b})\\}}<m+1.$

Consequently, we have

$\frac{|\ell(x)-\ell(x^{(i)\to b})|}{\ell(x)}\leq w(\\{x,x^{(i)\to
b}\\})\cdot\frac{\max\\{\ell(x),\ell(x^{(i)\to
b})\\}}{\min\\{\ell(x),\ell(x^{(i)\to b})\\}}\leq(m+1)\cdot w(\\{x,x^{(i)\to
b}\\})\leq 2m^{-\kappa+2}.$

Therefore, the contribution of each such edge to the sum on the LHS is at most
$4m^{-2\kappa+4}$.

Lastly, assume that $(x,x^{(i)\to b})$ is in $G^{[r]}$. By our construction,
this implies that $(x,x^{(i)\to b})$ is an even edge and there exists a
$c\in\mathbb{Z}_{m_{i}}\setminus\\{x_{i}\\}$ such that $(x,x^{(i)\to c})\in
G^{[u]}$. This also implies that $(x,x^{(i)\to b})$ is a level $\kappa$ edge,
for some $\kappa\geq 1$. By a similar argument as above, we have

$\left(\frac{\ell(x)-\ell(x^{(i)\to
b})}{\ell(x)}\right)^{2}\leq\left(w(\\{x,x^{(i)\to
b}\\})\cdot\frac{\max\\{\ell(x),\ell(x^{(i)\to
b})\\}}{\min\\{\ell(x),\ell(x^{(i)\to b})\\}}\right)^{2}\leq m^{2},$

which is at most $m^{2}\cdot(\text{outdegree of }x\text{ in }G^{[u]}\text{
with respect to edges in the {i}-th direction})$. Summing over all
$i\in\overline{T}$ and $b\in\mathbb{Z}_{m_{i}}\setminus\\{x_{i}\\}$ such that
$(x,x^{(i)\to b})\in G^{[r]}$, we find:

$\sum_{i\in\overline{T}}\sum_{\begin{subarray}{c}b\in\mathbb{Z}_{m_{i}}\\\
(x,x^{(i)\to b})\in G^{[r]}\end{subarray}}\left(\frac{\ell(x)-\ell(x^{(i)\to
b})}{\ell(x)}\right)^{2}\leq(m-1)m^{2}\cdot outdeg(x,G^{[u]}).$

The lemma follows by combining the analysis for edges in $G^{[u]},G^{[r]}$ and
$G^{[\kappa]}$. ∎

Finally, we connect $d_{TV}(\ell,\cal{U})$ with the expected
$\sqrt{\text{outdegree}}$ of $x\sim\ell$:

######  Lemma 19.

Letting $\beta=d_{TV}(\ell,\mathcal{U})$, one of the following two conditions
must hold:

  1. 1.

Either the directed graph $G^{[u]}$ of uneven edges satisfies:

$\mathbb{E}_{x\sim\ell}\left[\sqrt{\text{outdeg}(x,G^{[u]})}\right]\gtrsim\frac{\beta}{m^{3}\log^{2}n}.$

  2. 2.

Or, there exists a $\kappa\in[10\log(nm/\beta)]$ such that the directed graph
$G^{[\kappa]}$ satisfies:

$\mathbb{E}_{x\sim\ell}\left[\sqrt{\text{outdeg}(x,G^{[\kappa]})}\right]\gtrsim\frac{m^{\kappa}\beta}{m^{3.5}\cdot\log^{2}n\cdot\log(nm/\beta)}.$

###### Proof.

It follows from Lemmas 17 and 18 that

$\displaystyle\frac{\beta}{m^{1.5}\log^{2}n}$
$\displaystyle\lesssim\mathbb{E}_{x\sim\ell}\left[\sqrt{m^{3}\cdot\text{outdeg}(x,G^{[u]})+\sum_{\kappa\geq
1}4m^{-2\kappa+4}\cdot\text{outdeg}(x,G^{[\kappa]})}\right]$
$\displaystyle\leq
m^{1.5}\cdot\mathbb{E}_{x\sim\ell}\left[\sqrt{\text{outdeg}(x,G^{[u]})}\right]+\sum_{\kappa=1}^{10\log(nm/\beta)}2m^{-\kappa+2}\cdot\mathbb{E}_{x\sim\ell}\left[\sqrt{\text{outdeg}(x,G^{[\kappa]})}\right]+o\left(\frac{\beta}{m^{1.5}\log^{2}n}\right).$

which used the fact that the degrees are always bounded by $n(m-1)$. The lemma
follows. ∎

###  4.2 Separating into Cases

For each $t$-subset $T$ of $[n]$, let
$\alpha(T)=d_{TV}(p_{\overline{T}},\mathcal{U})$. Note that the $\alpha$ in
the statement of Lemma 9 can be written as
$\alpha=\mathbb{E}_{T\sim\mathcal{S}(t)}[\alpha(T)]$. For each $T$, take
$p_{\overline{T}}$ as $\ell$ in the previous subsection to partition
undirected edges in the undirected graph $\mathcal{H}(T)$ over
$\mathbb{Z}_{K}$ with $K=M_{\overline{T}}$ into $\smash{\mathcal{H}^{[z]}(T)}$
(zero edges), $\smash{\mathcal{H}^{[u]}(T)}$ (uneven edges), and
$\smash{\mathcal{H}^{[\kappa]}(T)}$ (even edges at scale $\kappa\geq 1$).
Orient these edges as in the previous subsection to obtain directed graphs
$G^{[u]}(T)$ and $G^{[\kappa]}(T)$. By applying Lemma 19 on
$\ell=p_{\overline{T}}$, we conclude that one of the following two conditions
holds for either $G^{[u]}(T)$ or one of the graphs $G^{[\kappa]}(T)$,
$\kappa\in[10\log(nm/\alpha(T))].$ These cases mirror the two cases in the
hypercube setting from [CCK+21].

Before stating the two cases, note that since $\alpha(T)\in[0,1]$, there
exists a $\zeta>0$ such that with probability at least $\zeta$ over
$T\sim\mathcal{S}(t)$,

$\alpha(T)\gtrsim\frac{\alpha}{\zeta\log(1/\alpha)}.$

Therefore, one of the following cases must hold.

Case 1: With probability at least $\zeta/2$ over $T\sim S(t)$, the directed
graph $G^{[u]}(T)$ of $p_{\overline{T}}$ satisfies

$\mathbb{E}_{x\sim
p_{\overline{T}}}\left[\sqrt{\text{outdeg}(x,G^{[u]}(T))}\right]\gtrsim\frac{\alpha}{\zeta\log(1/\alpha)\cdot
m^{3}\log^{2}n}.$

Since the out-degree is always between $0$ and $n(m-1)$, there exist two
parameters $d\in[n(m-1)]$ and $\xi>0$ such that with probability
$\zeta/(2\log(nm))$ over the draw of $T\sim S(t)$, we have

$\Pr_{x\sim p_{\overline{T}}}\left[d\leq\text{outdeg}(x,G^{[u]}(T))\leq
2d\right]\geq\xi$ (28)

and $\xi$ satisfies

$\sqrt{d}\cdot\xi\gtrsim\frac{\alpha}{\zeta\log(1/\alpha)\cdot
m^{3}\log^{2}n\cdot\log(nm)}.$ (29)

Case 2: There exists a $\kappa\in[O(\log(nm/\alpha))]$ (using $\zeta\leq 1$)
such that with probability at least

$\Omega\left(\frac{\zeta}{\log(nm/\alpha)}\right)$

over $T\sim S(t)$, the directed graph $G^{[\kappa]}(T)$ of even edges at scale
$\kappa$ of $p_{\overline{T}}$ satisfies

$\mathbb{E}_{x\sim
p_{\overline{T}}}\left[\sqrt{\text{outdeg}(x,G^{[\kappa]})(T)}\right]\gtrsim\frac{m^{\kappa}\alpha}{\zeta\log(1/\alpha)\cdot
m^{3.5}\log^{2}n\cdot\log(nm/\alpha)}.$

Using a bucketing argument, there exist $d\in[n(m-1)]$ and $\xi>0$ such that
with probability

$\Omega\left(\frac{\zeta}{\log(nm)\cdot\log(nm/\alpha)}\right)$

over the draw of $T\sim S(t)$, we have

$\mathbb{P}_{x\sim
p_{\overline{T}}}\left[d\leq\text{outdeg}(x,G^{[\kappa]}(T))\leq
2d\right]\geq\xi$

and $\xi$ satisfies

$\sqrt{d}\cdot\xi\gtrsim\frac{m^{\kappa}\alpha}{\zeta\log(1/\alpha)\cdot
m^{3.5}\log^{2}n\cdot\log(nm/\alpha)\cdot\log(nm)}.$ (30)

###  4.3 From Directed Graphs to the Bias Vector

Let $R$ be a subset of $[n]$ (which will be either a $t$-subset $T$ of $[n]$
or a $(t+1)$-subset $S$ of $[n]$ in the rest of the section). Let $J=M_{{R}}$.
Given a distribution $\ell$ over $\mathbb{Z}_{J}$, $i\in R$ and
$c,d\in\mathbb{Z}_{m_{i}}$, recall the definition of the bias
$\smash{\mu^{c,d}_{i}(\ell)}$ from Definition 4:

$\mu_{i}^{c,d}(\ell)=\frac{\Pr_{x\sim\ell}[x_{i}=c]-\Pr_{x\sim\ell}[x_{i}=d]}{\Pr_{x\sim\ell}[x_{i}=c]+\Pr_{x\sim\ell}[x_{i}=d]}$

with $\mu_{i}^{c,d}(\ell)=0$ with
$\Pr_{x\sim\ell}[x_{i}=c]=\Pr_{x\sim\ell}[x_{i}=d]=0$.

In this subsection we connect directed graphs defined in Section 4.1 and 4.2
to biases of restrictions $p_{|\rho}$ of $p$ when
$\rho\sim\mathcal{D}(t+1,p)$. Consider a distribution $p$ supported on
$\mathbb{Z}_{M}$ and let $t\in[n-1]$.

Let $\pi=(\pi(1),\dots,\pi(t+1))$ be an ordered sequence of $t+1$ distinct
indices from $[n]$. We let $S(\pi)$ denote the corresponding $(t+1)$-subset
$\\{\pi(1),\dots,\pi(t+1)\\}$.

######  Definition 20.

Given $\pi$ and $y\in\mathbb{Z}_{M}$, define a restriction
$\rho(\pi,y)\in\bigtimes_{i=1}^{n}(\mathbb{Z}_{m_{i}}\cup\\{*\\})$ as

$\rho(\pi,y)_{i}=\begin{cases}*~{}~{}~{}~{}i=\pi(j)\text{ for some
}j\in[t+1]\\\ y_{i}~{}~{}\text{ otherwise}.\end{cases}$

We will also consider sequences $\tau=(\tau(1),\dots,\tau(t))$ of $t$ (instead
of $t+1$) distinct indices from $[n]$. For such a $\tau$, the corresponding
set $S(\tau)$ and the restriction $\rho(\tau,y)$ given by $y\in\mathbb{Z}_{M}$
are defined similarly.

As in [CCK+21], we use that the following is an equivalent way of drawing
$\rho\sim\mathcal{D}(t+1,p)$:

  1. 1.

First, sample a sequence of $t+1$ random indices
$\pi=(\pi(1),\ldots,\pi(t+1))$ uniformly from $[n]$ without replacements (so
the set $S(\pi)$ can be viewed equivalently as drawn from $\mathcal{S}(t+1)$).

  2. 2.

Then, sample $y\sim p$.

  3. 3.

Finally, return $\rho=\rho(\pi,y)$.

We will use $(\pi,y)\sim\mathcal{D}^{\prime}(t+1,p)$ to denote the sampling of
$(\pi,y)$ as above, with the understanding that $\rho(\pi,y)$ is distributed
the same as $\mathcal{D}(t+1,p)$. Similarly, consider sampling
$\rho\sim\mathcal{D}(t,p)$ equivalently according to the following procedure:

  1. 1.

First, sample a sequence of $t$ random indices $\tau=(\tau(1),\dots,\tau(t))$
uniformly from $[n]$ without replacements (so the set $S(\tau)$ can be viewed
equivalently as drawn from $\mathcal{S}(t)$).

  2. 2.

Then, sample ${y}\sim p$.

  3. 3.

Finally, return $\rho=\rho(\tau,{y})$.

Similarly we will write $(\tau,y)\sim\mathcal{D}^{\prime}(t,p)$ to denote the
sampling of $(\tau,y)$ as above.

Fixing any $i\in[t+1]$, we let $\pi_{-i}$ denote the length-$t$ sequence
obtained from $\pi$ after removing its $i$-th entry. An important observation
is that $\rho\sim\mathcal{D}(t,p)$ can also be drawn as follows:

  1. 1.

First, sample a sequence of $t+1$ random indices
$\pi=(\pi(1),\ldots,\pi(t+1))$ uniformly from $[n]$ without replacements and
set $\tau=\pi_{-i}$. (Note that $i$ is a fixed index in $[t+1]$.)

  2. 2.

Then, sample $y\sim p$.

  3. 3.

Finally, return $y$ and $\rho=\rho(\tau,y)=\rho(\pi_{-i},y)$.

Given a $t$-subset $T$ of $[n]$ with $K=M_{\overline{T}}$, we will use

$(z,i,b)\in\mathbb{Z}_{K}\times\overline{T}\times\mathbb{Z}_{m_{i}}$

to denote directed edges over $\mathbb{Z}_{K}$: $(z,i,b)$ means the directed
edge $(z,z^{(i)\to b})$ so we can talk about, e.g., whether $(z,i,b)\in
G^{[u]}(T)$ and whether $(z,i,b)\in G^{[\kappa]}(T)$. (Note that for
notational convenience, we allow $b$ to be $z_{i}$, in which case $(z,i,b)$
can never be an edge in these directed graphs.) As an example, let
$y\in\mathbb{Z}_{M}$, $\pi$ be a $(t+1)$-sequence of distinct elements in
$[n]$, and $b\in\mathbb{Z}_{m_{\pi(i)}}$ for some $i\in[t+1]$. Then,
$\smash{(y_{\overline{S(\pi_{-i})}},\pi(i),b)}$ denotes the edge from
$\smash{y_{\overline{S(\pi_{-i})}}}$ to $y^{\prime}$ where $y^{\prime}$
satisfies $\smash{y^{\prime}_{\pi(i)}=b}$ and
$\smash{y^{\prime}_{\overline{S(\pi)}}=y_{\overline{S(\pi)}}}$.

The following lemma connects the directed graphs to biases of restrictions of
$p$:

######  Lemma 21.

Let $\pi$ be a $(t+1)$-sequence of distinct indices and $y\in\mathbb{Z}_{M}$.
For $i\in[t+1]$ and $b\in\mathbb{Z}_{m_{\pi(i)}}$,

$\displaystyle\left|\mu^{b,y_{\pi(i)}}_{\pi(i)}(p_{|\rho(\pi,y)})\right|$
$\displaystyle\geq\frac{m}{2(m+1)}\cdot\mathbbm{1}\left\\{\left(y_{\overline{S(\pi_{-i})}},\pi(i),b\right)\in
G^{[u]}(S(\pi_{-i}))\right\\}$ (31) $\displaystyle\hskip
22.76228pt+\sum_{\kappa\geq
1}\frac{1}{2m^{\kappa}}\cdot\mathbbm{1}\left\\{\left(y_{\overline{S(\pi_{-i})}},\pi(i),b\right)\in
G^{[\kappa]}(S(\pi_{-i}))\right\\}.$

###### Proof.

We let $\ell$ denote $p_{|\rho(\pi,y)}$ and $c$ denote $y_{\pi(i)}$. Writing

$\text{Pr}^{b}=\Pr_{x\sim
p}\left[x_{\pi(i)}=b,x_{\overline{S(\pi)}}=y_{\overline{S(\pi)}}\right]\quad\text{and}\quad\text{Pr}^{c}=\Pr_{x\sim
p}\left[x_{\pi(i)}=c,x_{\overline{S(\pi)}}=y_{\overline{S(\pi)}}\right],$

we have that the LHS of (31) is

$\left|\mu^{b,c}_{\pi(i)}(\ell)\right|=\left|\frac{\text{Pr}^{b}-\text{Pr}^{c}}{\text{Pr}^{b}+\text{Pr}^{c}}\right|.$

Let $z$ be the string with $z_{\overline{S(\pi)}}=y_{\overline{S(\pi)}}$ and
$z_{\pi(i)}=c$, and $z^{\prime}$ be with
$z^{\prime}_{\overline{S(\pi)}}=y_{\overline{S(\pi)}}$ and
$z^{\prime}_{\pi(i)}=b$. Then

$w({z,z^{\prime}})=\frac{|\text{Pr}^{c}-\text{Pr}^{b}|}{\max\\{\text{Pr}^{c},\text{Pr}^{b}\\}}\leq
2\cdot\left|\mu^{b,c}_{\pi(i)}(\ell)\right|.$

If $(z,\pi(i),b)\in G^{[u]}(T)$ is uneven, then the weight is at least
${m}/({m+1})$; if $(z,\pi(i),b)\in G^{[\kappa]}(T)$ for some $\kappa\geq 1$,
then the weight is at least $m^{-\kappa}$. This finishes the proof of the
lemma. ∎

###  4.4 Case 1: Graph with Uneven Edges

We assume there are parameters $\zeta^{\prime},\xi$, and $d\geq 1$ such that
with probability at least $\zeta^{\prime}$ over $T\sim\mathcal{S}(t)$,

$\Pr_{x\sim p_{\overline{T}}}\left[d\leq\text{outdeg}(x,G^{[u]}(T))\leq
2d\right]\geq\xi.$ (32)

Notice that $\zeta^{\prime}=\zeta/(2\log(nm))$ (see Case 1 of Section 4.2), so
that (29) implies:

$\sqrt{d}\cdot\xi\gtrsim\frac{\alpha}{\zeta^{\prime}\log(1/\alpha)\cdot
m^{3}\log^{4}(nm)}.$ (33)

We define $(\tau,y)$, where $\tau$ is a $t$-sequence and $y\in\mathbb{Z}_{M}$,
to be $t$-contributing or $(t+1)$-contributing:

######  Definition 22.

Let $\tau$ be a $t$-sequence of distinct indices from $[n]$ and let
$y\in\mathbb{Z}_{M}$. We say the pair $(\tau,y)$ is $t$-contributing if the
restricted distribution $p_{|\rho(\tau,y)}$ satisfies

$\Big{\|}\mu\left(p_{|\rho(\tau,y)}\right)\Big{\|}_{2}\geq\frac{1}{m}\cdot\sqrt{\frac{d}{32}},$

and we say $(\tau,y)$ is $(t+1)$-contributing otherwise.

Lemma 9 would follow if there are many $t$-contributing pairs $(\tau,y)$. The
next lemma gives us the tool we need to obtain $t$-contributing pairs:

######  Lemma 23.

Let $\pi$ be a $(t+1)$-sequence of distinct indices from $[n]$, and
$y\in\mathbb{Z}_{M}$ be in the support of $p$. If there are distinct
$i_{1},...,i_{d+1}\in[t+1]$ such that for each $k\in[d+1]$ there is a
$b_{k}\in\mathbb{Z}_{m_{\pi(i_{k})}}$ such that

$\left(y_{\overline{S(\pi_{-{i_{k}}})}},\pi(i_{k}),b_{k}\right)\in
G^{[u]}\left(S(\pi_{-i_{k}})\right),$

then $(\pi_{-i_{k}},y)$ is a $t$-contributing pair for at least one of the
indices $k\in[d+1]$.

We begin by proving the following claim.

######  Claim 24.

Let $\pi$ be a $(t+1)$-sequence of distinct indices from $[n]$, and let
$y\in\mathbb{Z}_{M}$ be in the support of $p$. If there are $i\neq j\in[d+1]$,
$b_{i}\in\mathbb{Z}_{m_{\pi(i)}}$ and $b_{j}\in\mathbb{Z}_{m_{\pi(j)}}$ such
that

$\left(y_{\overline{S(\pi_{-{i}})}},\pi(i),b_{i}\right)\in
G^{[u]}\left(S(\pi_{-i})\right)\quad\text{and}\quad\left(y_{\overline{S(\pi_{-{j}})}},\pi(j),b_{j}\right)\in
G^{[u]}\left(S(\pi_{-j})\right),$

then there must exist either a $c_{i}\in\mathbb{Z}_{m_{\pi(i)}}$ or
$c_{j}\in\mathbb{Z}_{m_{\pi(j)}}$ such that either

$\left|\mu^{c_{i},y_{\pi(i)}}_{\pi(i)}\left(p_{|\rho(\pi_{-j},y)}\right)\right|\geq\frac{1}{4m}\quad\text{or}\quad\left|\mu^{c_{j},y_{\pi(j)}}_{\pi(j)}\left(p_{|\rho(\pi_{-i},y)}\right)\right|\geq\frac{1}{4m}.$

Intuition behind the proof: We proceed by contradiction and assume for all
$c_{i}$ and $c_{j}$, we have

$\left|\mu^{c_{i},y_{\pi(i)}}_{\pi(i)}\left(p_{|\rho(\pi_{-j},y)}\right)\right|<\frac{1}{4m}\quad\text{and}\quad\left|\mu^{c_{j},y_{\pi(j)}}_{\pi(j)}\left(p_{|\rho(\pi_{-i},y)}\right)\right|<\frac{1}{4m}.$
(34)

Then all the probabilities

$\Pr_{x\sim
p}\left[x_{\pi(i)}=c_{i},x_{\pi(j)}=y_{\pi(j)},x_{\overline{S(\pi)}}=y_{\overline{S(\pi)}}\right]\quad\text{and}\quad\Pr_{x\sim
p}\left[x_{\pi(i)}=y_{\pi(i)},x_{\pi(j)}=c_{j},x_{\overline{S(\pi)}}=y_{\overline{S(\pi)}}\right]$

must be close to the probability

$\Pr_{x\sim
p}\left[x_{\pi(i)}=y_{\pi(i)},x_{\pi(j)}=y_{\pi(j)},x_{\overline{S(\pi)}}=y_{\overline{S(\pi)}}\right].$

In particular, this implies that

$\Pr_{x\sim
p}\left[x_{\pi(i)}=b_{i},x_{\pi(j)}=y_{\pi(j)},x_{\overline{S(\pi)}}=y_{\overline{S(\pi)}}\right]\approx\Pr_{x\sim
p}\left[x_{\pi(i)}=y_{\pi(i)},x_{\pi(j)}=y_{\pi(j)},x_{\overline{S(\pi)}}=y_{\overline{S(\pi)}}\right].$
(35)

However, this leads to a contradiction since we can use

$\Pr_{x\sim
p}\left[x_{\pi(i)}=y_{\pi(i)},x_{\pi(j)}=c_{j},x_{\overline{S(\pi)}}=y_{\overline{S(\pi)}}\right]\approx\Pr_{x\sim
p}\left[x_{\pi(i)}=y_{\pi(i)},x_{\pi(j)}=y_{\pi(j)},x_{\overline{S(\pi)}}=y_{\overline{S(\pi)}}\right].$

and the unevenness of the edge

$\left(y_{\overline{S(\pi_{-{i}})}},\pi(i),b_{i}\right)$

to show that the LHS of (35) is smaller than its RHS, a contradiction.

###### Proof of Claim 24.

Suppose towards a contradiction that (34) holds. Also for notational
convenience we assume that $\pi(i)=1$ and $\pi(j)=2$. From the first part of
(34) we have

$\left|\frac{\Pr_{x\sim
p}[x_{1}=y_{1},x_{2}=y_{2},x_{\overline{S(\pi)}}=y_{\overline{S(\pi)}}]-\Pr_{x\sim
p}[x_{1}=c_{i},x_{2}=y_{2},x_{\overline{S(\pi)}}=y_{\overline{S(\pi)}}]}{\Pr_{x\sim
p}[x_{1}=y_{1},x_{2}=y_{2},x_{\overline{S(\pi)}}=y_{\overline{S(\pi)}}]+\Pr_{x\sim
p}[x_{1}=c_{i},x_{2}=y_{2},x_{\overline{S(\pi)}}=y_{\overline{S(\pi)}}]}\right|<\frac{1}{4m}.$

Letting $\gamma:=\Pr_{x\sim
p}[x_{1}=y_{1},x_{2}=y_{2},x_{\overline{S(\pi)}}=y_{\overline{S(\pi)}}]>0$
(note that $\gamma>0$ because we assumed that $y$ is in the support of $p$),
this implies for any $c_{i}\neq y_{1}$, we have

$\displaystyle\gamma\cdot\frac{1-\frac{1}{4m}}{1+\frac{1}{4m}}<\Pr_{x\sim
p}\left[x_{1}=c_{i},x_{2}=y_{2},x_{\overline{S(\pi)}}=y_{\overline{S(\pi)}}\right]<\gamma\cdot\frac{1+\frac{1}{4m}}{1-\frac{1}{4m}}.$
(36)

Similarly, for any $c_{j}\neq y_{\pi(j)}$, we have

$\displaystyle\gamma\cdot\frac{1-\frac{1}{4m}}{1+\frac{1}{4m}}<\Pr_{x\sim
p}\left[x_{1}=y_{1},x_{2}=c_{j},x_{\overline{S(\pi)}}=y_{\overline{S(\pi)}}\right]<\gamma\cdot\frac{1+\frac{1}{4m}}{1-\frac{1}{4m}}.$
(37)

In particular, setting $c_{i}=b_{i}$, we have

$\Pr_{x\sim
p}\left[x_{1}=b_{i},x_{\overline{S(\pi)}}=y_{\overline{S(\pi)}}\right]\geq\Pr_{x\sim
p}\left[x_{1}=b_{i},x_{2}=y_{2},x_{\overline{S(\pi)}}=y_{\overline{S(\pi)}}\right]>\gamma\cdot\frac{1-\frac{1}{4m}}{1+\frac{1}{4m}}.$
(38)

On the other hand, given that

$\left(y_{\overline{S(\pi_{-{i}})}},\pi(i),b_{i}\right)\in
G^{[u]}\left(S(\pi_{-i})\right),$

we have

$\frac{|\Pr_{x\sim
p}[x_{1}=y_{1},x_{\overline{S(\pi)}}=y_{\overline{S(\pi)}}]-\Pr_{x\sim
p}[x_{1}=b_{i},x_{\overline{S(\pi)}}=y_{\overline{S(\pi)}}]|}{\max\\{\Pr_{x\sim
p}[x_{1}=y_{1},x_{\overline{S(\pi)}}=y_{\overline{S(\pi)}}],\Pr_{x\sim
p}[x_{1}=b_{i},x_{\overline{S(\pi)}}=y_{\overline{S(\pi)}}]\\}}\geq\frac{m}{m+1}.$

By the orientation of uneven edges, we have

$\Pr_{x\sim
p}\left[x_{1}=y_{1},x_{\overline{S(\pi)}}=y_{\overline{S(\pi)}}\right]\geq\Pr_{x\sim
p}\left[x_{1}=b_{i},x_{\overline{S(\pi)}}=y_{\overline{S(\pi)}}\right].$

As a result, we have

$\Pr_{x\sim
p}\left[x_{1}=b_{i},x_{\overline{S(\pi)}}=y_{\overline{S(\pi)}}\right]\leq\frac{1}{m+1}\cdot\Pr_{x\sim
p}\left[x_{1}=y_{1},x_{\overline{S(\pi)}}=y_{\overline{S(\pi)}}\right].$ (39)

Finally, using (37), we have

$\Pr_{x\sim
p}\left[x_{1}=y_{1},x_{\overline{S(\pi)}}\right]\leq\gamma\left(1+(m_{2}-1)\cdot\frac{1+\frac{1}{4m}}{1-\frac{1}{4m}}\right)\leq\gamma\left(1+(m-1)\cdot\frac{1+\frac{1}{4m}}{1-\frac{1}{4m}}\right)$

This together with (38) and (39) lead to a contradiction. ∎

We are now ready to prove Lemma 23.

###### Proof of Lemma 23.

Suppose there are $d+1$ distinct indices $i_{1},...,i_{d+1}\in[t+1]$ such that
for each index $k\in[d+1]$ there exists a
$b_{k}\in\mathbb{Z}_{m_{\pi(i_{k})}}$ such that

$\left(y_{\overline{S(\pi_{-{i_{k}}})}},\pi(i_{k}),b_{k}\right)\in
G^{[u]}\left(S(\pi_{-i_{k}})\right).$

By Claim 24, for each pair $i,j$ of the $d+1$ indices, there exists $c_{i}$ or
$c_{j}$ such that either

$\left|\mu^{c_{i},y_{\pi(i)}}_{\pi(i)}\left(p_{|\rho(\pi_{-j},y)}\right)\right|\geq\frac{1}{4m}\quad\text{or}\quad\left|\mu^{c_{j},y_{\pi(j)}}_{\pi(j)}\left(p_{|\rho(\pi_{-i},y)}\right)\right|\geq\frac{1}{4m}.$
(40)

Construct a graph $G$ as follows. Let its vertex set be
$i_{1},\ldots,i_{d+1}$. For each pair $i,j$, create a directed edge from $i$
to $j$ if the second part of (40) holds and create a directed edge from $j$ to
$i$ if if the second part of (40) holds. If both inequalities hold, orient the
edge between $i$ and $j$ arbitrarily. So $G$ a directed version of the
complete undirected graph over $i_{1},\ldots,i_{d+1}$.

It is easy to show that $G$ has a vertex with out-degree $\geq d/2$; otherwise
the total number of edges is $<(d+1)\cdot(d/2)$, a contradiction. To finish
the proof, let $k$ be an index among $i_{1},\ldots,i_{d+1}$ that has out-
degree at least $d/2$. Then we have

$\Big{\|}\mu\left(p_{|\rho(\pi_{-k},y)}\right)\Big{\|}_{2}^{2}\geq\frac{1}{(4m)^{2}}\cdot\frac{d}{2},$

and the lemma follows. ∎

We now use Lemma 23 to prove Case 1 of Lemma 9. We will need to lowerbound the
expectation of $\|\mu(p_{|\rho(\pi,y)|})\|_{2}$ as
$(\pi,y)\sim\mathcal{D}^{\prime}(t+1,p)$. For each $i\in[t+1]$, let $X_{i}$ be
the indicator random variable that is set to $1$ when the following event
holds:

$\left\\{\left(y_{\overline{S(\pi_{-{i}})}},\pi(i),b\right)\in
G^{[u]}\left(S(\pi_{-i})\right)\text{ for some
}b\in\mathbb{Z}_{m_{\pi(i)}}\text{\ and\ }(\pi_{-i},y)\text{ is
}(t+1)\text{-contributing}\right\\}.$ (41)

First, combining Lemma 21 and the first part of the event above gives us the
following inequality:

$\Big{\|}\mu\left(p_{|\rho(\pi,y)}\right)\Big{\|}_{2}\geq\frac{m}{2(m+1)}\cdot\sqrt{X_{1}+\dots+X_{t+1}}.$

This is because Lemma 21 implies that

$\displaystyle\Big{\|}\mu\left(p_{|\rho(\pi,y)}\right)\Big{\|}_{2}^{2}$
$\displaystyle\geq\sum_{i\in[t+1]}\sum_{c\in\mathbb{Z}_{m_{\pi(i)}}}\left(\frac{m}{2(m+1)}\right)^{2}\cdot\mathbbm{1}\left\\{\left(y_{\overline{S(\pi_{-i})}},\pi(i),c\right)\in
G^{[u]}\left(S(\pi_{-i})\right)\right\\}$
$\displaystyle\geq\left(\frac{m}{2(m+1)}\right)^{2}\cdot\big{(}X_{1}+\cdots+X_{t+1}\big{)}.$

Second, we can use Lemma 23 and the second part of (41) to see that
$X_{1}+\dots+X_{t+1}$ is at most $d$ with probability $1$. Therefore, we can
obtain the following expression:

$\mathbb{E}_{(\pi,y)}\left[\Big{\|}\mu\left(p_{|\rho(\pi,y)}\right)\Big{\|}_{2}\right]\gtrsim\mathbb{E}_{(\pi,y)}\big{[}X_{1}+\dots+X_{t+1}\big{]}\cdot\frac{1}{\sqrt{d}}\cdot\frac{m}{2(m+1)},$

where $(\pi,y)\sim\mathcal{D}^{\prime}(t+1,p)$.

What remains is bounding the probability of $X_{i}=1$ for each $i\in[t+1]$.
The proof of this part is exactly the same as in [CCK+21], and we include it
for completeness. We claim that for each $i\in[t+1]$,

$\Pr_{(\pi,y)}\big{[}X_{i}=1\big{]}\geq\left(\zeta^{\prime}\xi-\Pr_{(\pi,y)}\big{[}(\pi_{-i},y)\text{
is }t\text{-contributing})\big{]}\right)\cdot\frac{d}{nm}.$ (42)

Let us consider drawing $\pi$ and $y$ by drawing $y$ and $\pi_{-i}$ first and
then $\pi(i)$. We define event $F$ over $y$ and $\pi_{-i}$ as follows:

Event $F$: $S(\pi_{-i})$ as $T$ and $y_{\overline{S(\pi_{-i}})}$ as $x$
satisfy (32) and $(\pi_{-i},y)$ is $(t+1)$-contributing.

From our assumption at the beginning of Case 1, the first part of $F$ occurs
with probability at least $\zeta^{\prime}\xi$. Therefore, the probability of
$F$ is at least

$\zeta^{\prime}\xi-\Pr_{(\pi,y)}\big{[}(\pi_{-i},y)\text{ is
}t\text{-contributing}\big{]}.$

Conditioning on $\pi_{-i}$ and $y$ satisfying $F$, $\pi(i)$ (together with
$\pi_{-i}$ and $y$) leads to $X_{i}=1$ if there exists $b$ such that
$(y_{\overline{S(\pi_{-{i}})}},\pi(i),b)\in G^{[u]}(S(\pi_{-i}))$. The
probability of this is at least ${d}/({n(m-1)})$.

Continuing from (42), next we can observe that the probability of
$(\pi_{-i},y)$ being $t$-contributing is the same as $(\tau,y)$ being
$t$-contributing, where $(\tau,y)\sim\mathcal{D}^{\prime}(t,p)$. Putting
everything together yields

$\mathbb{E}_{(\pi,y)}\left[\Big{\|}\mu\left(p_{|\rho(\pi,y)}\right)\Big{\|}_{2}\right]\gtrsim\frac{1}{\sqrt{d}}\cdot(t+1)\cdot\left(\zeta^{\prime}\xi-\Pr_{(\tau,y)}\big{[}(\tau,y)\text{
is }t\text{-contributing}\big{]}\right)\cdot\frac{d}{nm}.$ (43)

Thus, either the probability of $(\tau,y)$ being $t$-contributing is at least
$\zeta^{\prime}\xi/2$, in which case we have

$\mathbb{E}_{(\tau,y)\sim\mathcal{D}^{\prime}(t,p)}\left[\Big{\|}\mu\left(p_{|\rho(\tau,y)}\right)\Big{\|}_{2}\right]\gtrsim\zeta^{\prime}\xi\cdot\frac{\sqrt{d}}{m}\gtrsim\frac{\alpha}{m^{4}\cdot\log^{4}(nm)\log(1/\alpha)}$

using (33) for the last inequality, from which (2) follows as $t+1\leq n$. Or,
(43) can be lowerbounded by:

$\frac{1}{\sqrt{d}}\cdot(t+1)\cdot{\zeta^{\prime}\xi}\cdot\frac{d}{nm}\gtrsim\frac{t}{n}\cdot\frac{\alpha}{m^{4}\cdot\log^{4}(nm)\log(1/\alpha)}.$

This finishes the proof of Case 1.

###  4.5 Case 2: Graph with Even Edges

From Case 2 of Section 4.2, we assume that there are parameters
$\kappa\in[O(\log(nm/\alpha))]$, $\zeta^{\prime},\xi$, and $d$ such that with
probability at least $\zeta^{\prime}$ over the draw of $T\sim\mathcal{S}(t)$,
we have:

$\mathbb{P}_{x\sim
p_{\overline{T}}}\left[d\leq\text{outdeg}(x,G^{[\kappa]}(T))\leq
2d\right]\geq\xi,$

where (30) implies that:

$\sqrt{d}\cdot\xi\gtrsim\frac{m^{\kappa}\alpha}{\zeta^{\prime}\log(1/\alpha)\cdot
m^{3.5}\cdot\log^{2}n\log^{2}(nm)\log^{2}(nm/\alpha)}.$

We introduce a notion of $t$-contributing and $(t+1)$-contributing
restrictions:

######  Definition 25.

Let $\gamma\geq 1$ be a parameter to be fixed later. (We will set $\gamma$ to
be $d$ at the end but we keep it as a parameter for now.) A restriction $\rho$
with $t$ stars is said to be $t$-contributing if

$\Big{\|}\mu\left(p_{|\rho}\right)\Big{\|}_{2}\geq\frac{\sqrt{\gamma}}{m^{\kappa+1}},$

and we say that $\rho$ is $(t+1)$-contributing otherwise.

######  Lemma 26.

Let $\pi$ be a $(t+1)$-sequence of distinct indices from $[n]$ and let
$y\in\mathbb{Z}_{M}$ be in the support of $p$. If $i\in[t+1]$ satisfies that
$\rho(\pi_{-i},y^{(\pi(i))\to a})$ is $(t+1)$-contributing for all
$a\in\mathbb{Z}_{m_{\pi(i)}}$, then

$\sum_{j\in[t+1]\setminus\\{i\\}}\sum_{c,d\in\mathbb{Z}_{m_{\pi(j)}}}\left(\mu^{c,d}_{\pi(j)}\left(p_{|\rho(\pi,y)}\right)\right)^{2}<\frac{\gamma}{m^{2\kappa+2}}.$

###### Proof.

Let

$\Pr(a):=\Pr_{x\sim p}\big{[}x_{\pi(i)}=a\hskip 1.42271pt|\hskip
1.42271ptx_{\overline{S(\pi)}}=y_{\overline{S(\pi)}}\big{]}$

for each $a\in\mathbb{Z}_{m_{\pi(i)}}$. We note that for any $j\neq i$ and
$c,d\in\mathbb{Z}_{m_{\pi(j)}}$,

$\mu^{c,d}_{\pi(j)}\left(p_{|\rho(\pi,y)}\right)=\sum_{a\in\mathbb{Z}_{m_{\pi(i)}}}\Pr(a)\cdot\mu^{c,d}_{\pi(j)}\left(p_{|\rho(\pi_{-i},y^{(\pi(i))\to
a})}\right).$

By Jensen’s inequality, we have

$\sum_{j\in[t+1]\setminus\\{i\\}}\sum_{c,d\in\mathbb{Z}_{m_{\pi(j)}}}\left(\mu^{c,d}_{\pi(j)}\left(p_{|\rho(\pi,y)}\right)\right)^{2}\leq\sum_{j\in[t+1]\setminus\\{i\\}}\sum_{c,d\in\mathbb{Z}_{m_{\pi(j)}}}\sum_{a\in\mathbb{Z}_{m_{\pi(i)}}}\Pr(a)\cdot\left(\mu^{c,d}_{\pi(j)}\left(p_{|\rho(\pi_{-i},y^{(\pi(i))\to
a})}\right)\right)^{2}$

Since we assume each pair $(\pi_{-i},y^{(\pi(i))\to a})$ is
$(t+1)$-contributing, we have

$\sum_{j\in[t+1]\setminus\\{i\\}}\sum_{c,d\in\mathbb{Z}_{m_{\pi(j)}}}\left(\mu^{c,d}_{\pi(j)}\left(p_{|\rho(\pi_{-i},y^{(\pi(i))\to
a})}\right)\right)^{2}<\frac{\gamma}{m^{2\kappa+2}}$

for each such $\rho(\pi_{-i},y^{(\pi(i))\to a})$. The lemma follows using
$\sum_{a}\Pr(a)=1$. ∎

Similar to Case 1 we would like to lowerbound the expectation of
$\|\mu(p_{|\rho(\pi,y)})\|_{2}$ as $(\pi,y)\sim\mathcal{D}^{\prime}(t+1,p)$.
Let us introduce the following indicator random variable $X_{i}$ for each
$i\in[t+1]$. $X_{i}$ equals $1$ when the following event $F_{i}$ holds:

> Event $F_{i}$ on $(\pi,y)\sim\mathcal{D}^{\prime}(t+1,p)$: There exists a
> $b\in\mathbb{Z}_{m_{\pi(i)}}$ such that
>
> $\left(y_{\overline{S(\pi_{-i})}},\pi(i),b\right)\in
> G^{[\kappa]}\left(S(\pi_{-i})\right),$
>
> and for all $c\in\mathbb{Z}_{m_{\pi(i)}}$, we have that
> $\rho(\pi_{-i},y^{\pi(i)\to c})$ is $(t+1)$-contributing.

Combining Lemma 21 and the first part of the event $F_{i}$ gives us

$\Big{\|}\mu\left(p_{|\rho(\pi,y)}\right)\Big{\|}_{2}\geq\frac{1}{2m^{\kappa}}\cdot\sqrt{X_{1}+\dots+X_{t+1}}.$

Combining this inequality with Lemma 26 and the second part of Event $F_{i}$
implies that $X_{1}+\dots+X_{t+1}$ is at most $\lceil 8\gamma/m^{2}\rceil$
with probability $1$. This is because if the sum is more than $\lceil
8\gamma/m^{2}\rceil$, there are two $X_{i}=X_{j}=1$, from which Lemma 26
implies that

$\frac{1}{4m^{2\kappa}}\cdot(X_{1}+\dots+X_{t+1})\leq\Big{\|}\mu\left(p_{|\rho(\pi,y)}\right)\Big{\|}_{2}^{2}=\sum_{i\in[t+1]}\sum_{c,d\in\mathbb{Z}_{m_{\pi(i)}}}\left(\mu^{c,d}_{\pi(i)}\left(p_{|\rho(\pi,y)}\right)\right)^{2}<2\cdot\frac{\gamma}{m^{2\kappa+2}},$

which implies that $X_{1}+\dots+X_{t+1}<{8\gamma}/{m^{2}}$. As a result, we
have

$\mathbb{E}_{(\pi,y)}\left[\Big{\|}\mu\left(p_{|\rho(\pi,y)}\right)\Big{\|}_{2}\right]\gtrsim\frac{1}{m^{\kappa}}\cdot\mathbb{E}_{(\pi,y)}\big{[}X_{1}+\dots+X_{t+1}\big{]}\cdot\sqrt{\frac{1}{\lceil
8\gamma/m^{2}\rceil}}.$

What remains is bounding the probability that $X_{i}=1$.

To do so, we will need to introduce some notation. Let $T$ be a size-$t$
subset of $[n]$ and let
$\smash{z\in\bigtimes_{i\in\overline{T}}\mathbb{Z}_{m_{i}}}$. We write
$\rho(z)$ to denote the restriction
$\smash{\rho\in\bigtimes_{i=1}^{n}(\mathbb{Z}_{m_{i}}\cup\\{*\\})}$ with
$\rho_{i}=z_{i}$ for all $i\in\overline{T}$ and $\rho_{i}=\ast$ for all $i\in
T$. Define the following two disjoint subsets for each size-$t$ subset $T$:

$\displaystyle A_{T}$
$\displaystyle=\left\\{z\in\bigtimes_{i\in\overline{T}}\mathbb{Z}_{m_{i}}:d\leq\text{outdeg}\left(z,G^{[\kappa]}(T)\right)\leq
2d\text{ and }\rho(z)\text{ is }(t+1)\text{-contributing}\right\\}$
$\displaystyle B_{T}$
$\displaystyle=\left\\{w\in\bigtimes_{i\in\overline{T}}\mathbb{Z}_{m_{i}}:\rho(w)\text{
is }t\text{-contributing}\right\\}.$

It is not hard to see that the probability of $X_{i}=1$ (i.e. the event
$F_{i}$ on $(\pi,y)\sim\mathcal{D}^{\prime}(t+1,p)$) is at least the
probability of the following event $E$, where we first draw a $t$-subset $T$
of $[n]$ uniformly at random, then $z\sim p_{\overline{T}}$, and finally draw
$i$ from $\overline{T}$ uniformly at random:

$\text{Event }E:\exists\hskip
1.42271ptb\in\mathbb{Z}_{m_{i}}:\left(z,i,b\right)\in G^{[\kappa]}(T),z\in
A_{T}\text{, and }\forall\hskip 1.42271ptc\in\mathbb{Z}_{m_{i}}:z^{(i)\to
c}\not\in B_{T}.$

We now lowerbound the probability of $E$ over $T,z$ and $i$. First, we write
the probability as follows:

$\displaystyle\Pr_{T,z,i}\big{[}E\big{]}=\Pr_{T,z,i}\left[\exists\hskip
1.42271ptb\in\mathbb{Z}_{m_{i}}:(z,i,b)\in G^{[\kappa]}(T)\text{\ and\ }z\in
A_{T}\right]$ (44) $\displaystyle\hskip
14.22636pt-\Pr_{T,z,i}\left[\exists\hskip
1.42271ptb\in\mathbb{Z}_{m_{i}}:(z,i,b)\in G^{[\kappa]}(T),z\in A_{T}\text{\
and }\exists\hskip 1.42271ptc\in\mathbb{Z}_{m_{i}}:z^{(i)\to c}\in
B_{T}\right].$

The first probability on the right hand side of (44) is at least:

$\left(\zeta^{\prime}\xi-\Pr_{T,z}\big{[}\rho(z)\text{ is
}t\text{-contributing}\big{]}\right)\cdot\frac{d}{(n-t)m}.$

To see this, we first draw $T$ and $z$ and then impose the condition that
$z\in A_{T}$. Similarly to the Case 1 arguments, the probability of such an
event is at least:

$\zeta^{\prime}\xi-\Pr_{T,z}\big{[}\rho(z)\ \text{is
$t$-contributing}\big{]}.$

We then draw $i$ from $\overline{T}$. The probability of getting an
$(z,i,b)\in G^{[\kappa]}(T)$ for some $b$ is at least

$\frac{d}{(n-t)(m-1)}>\frac{d}{(n-t)m}.$

Next we upperbound the probability that is being subtracted in (44). It can be
written as:

$\frac{1}{\binom{n}{t}}\sum_{T\in\mathcal{P}(t)}\sum_{z}\Pr_{x\sim
p_{\overline{T}}}[x=z]\sum_{i\in\overline{T}}\frac{1}{|\overline{T}|}\cdot\mathbbm{1}\left\\{\exists\hskip
1.42271ptb\in\mathbb{Z}_{m_{i}}:(z,i,b)\in G^{[\kappa]}(T),z\in
A_{T},\exists\hskip 1.42271ptc\in\mathbb{Z}_{m_{i}}:z^{(i)\to c}\in
B_{T}\right\\},$

where the sum of $z$ is over
$z\in\bigtimes_{i\in\overline{T}}\mathbb{Z}_{m_{i}}$. By a union bound, we can
write this as:

$\displaystyle\frac{1}{\binom{n}{t}(n-t)}\sum_{T\in\mathcal{P}(t)}\sum_{z}\Pr_{x\sim
p_{\overline{T}}}[x=z]\sum_{i\in\overline{T}}\sum_{b\in\mathbb{Z}_{m_{i}}}\sum_{c\in\mathbb{Z}_{m_{i}}}\mathbbm{1}\left\\{(z,i,b)\in
G^{[\kappa]}(T)\land z\in A_{T}\land z^{(i)\to c}\in B_{T}\right\\}$
$\displaystyle=\frac{1}{\binom{n}{t}(n-t)}\sum_{T\in\mathcal{P}(t)}\sum_{i\in\overline{T}}\sum_{a\in\mathbb{Z}_{m_{i}}}\sum_{z:z_{i}=a}\sum_{b\in\mathbb{Z}_{m_{i}}}\sum_{c\in\mathbb{Z}_{m_{i}}}\Pr_{x\sim
p_{\overline{T}}}[x=z]\cdot\mathbbm{1}\left\\{(z,i,b)\in G^{[\kappa]}(T)\land
z\in A_{T}\land z^{(i)\to c}\in B_{T}\right\\}$

We apply a change of variables. Instead of summing over all $a$ and all
$\smash{z\in\bigtimes_{i\in\overline{T}}\mathbb{Z}_{m_{i}}:z_{i}=a}$, we sum
over all $c\in\mathbb{Z}_{m_{i}}$, and all
$\smash{w\in\bigtimes_{i\in\overline{T}}\mathbb{Z}_{m_{i}}:w_{i}=c}$. Observe
that the original variable $z$ changes to $w^{(i)\to a}$, and $z^{(i)\to c}$
becomes $w$. This yields the following expression:

$\frac{1}{\binom{n}{t}(n-t)}\sum_{T}\sum_{i\in\overline{T}}\sum_{c\in\mathbb{Z}_{m_{i}}}\sum_{w:w_{i}=c}\sum_{a,b\in\mathbb{Z}_{m_{i}}}\Pr_{x\sim
p_{\overline{T}}}[x=w^{(i)\to a}]\cdot\mathbbm{1}\left\\{(w^{(i)\to a},i,b)\in
G^{[\kappa]}(T)\land w^{(i)\to a}\in A_{T}\land w\in B_{T}\right\\}.$

Observe that if $\smash{(w^{(i)\to a},w^{(i)\to b})}$ is not an edge in
$G^{[\kappa]}(T)$, then the corresponding indicator variable above equals
zero. Otherwise, if it is an edge in $\smash{G^{[\kappa]}(T)}$, by our
construction of $G^{[\kappa]}(T)$, we must have $(w^{(i)\to a},w^{(i)\to
d})\not\in G^{[u]}(T)$ for all $d\in\mathbb{Z}_{m_{i}}$. Therefore, we have

$\Pr_{x\sim p_{\overline{T}}}\left[x=w^{(i)\to
a}\right]\leq(m+1)\cdot\Pr_{x\sim p_{\overline{T}}}\left[x=w^{(i)\to
d}\right]$

for all $d\in\mathbb{Z}_{m_{i}}$. Therefore, the expression can be bounded
from above by

$\displaystyle\frac{(m+1)}{\binom{n}{t}(n-t)}\sum_{T}\sum_{i\in\overline{T}}\sum_{c\in\mathbb{Z}_{m_{i}}}\sum_{w:w_{i}=c}\sum_{a,b\in\mathbb{Z}_{m_{i}}}\Pr_{x\sim
p_{\overline{T}}}[x=w]\cdot\mathbbm{1}\left\\{(w^{(i)\to a},i,b)\in
G^{[\kappa]}(T)\land w^{(i)\to a}\in A_{T}\land w\in B_{T}\right\\}$
$\displaystyle=\frac{(m+1)}{\binom{n}{t}(n-t)}\sum_{T}\sum_{w\in
B_{T}}\Pr_{x\sim
p_{\overline{T}}}[x=w]\sum_{i\in\overline{T}}\sum_{a,b\in\mathbb{Z}_{m_{i}}}\mathbbm{1}\left\\{(w^{(i)\to
a},i,b)\in G^{[\kappa]}(T)\land w^{(i)\to a}\in A_{T}\right\\}.$

Next, considering the sum of the indicator over all $i\in\overline{T}$ and all
$a\in\mathbb{Z}_{m_{i}}$ yields all possible ways to get to $w^{(i)\to b}$
from $A_{T}$ in $G^{[\kappa]}(T)$. Thus our expression equals:

$\frac{(m+1)}{\binom{n}{t}(n-t)}\sum_{T\in\mathcal{P}(t)}\sum_{w\in
B_{T}}\Pr_{x\sim
p_{\overline{T}}}[x=w]\sum_{b\in\mathbb{Z}_{m_{i}}}\left[\text{number of edges
from }A_{T}\text{ to }w^{(i)\to b}\text{ in }G^{[\kappa]}(T)\right].$

Because each vertex in $A_{T}$ has out-degree at most $2d$ in
$G^{[\kappa]}(T)$, we may apply Lemma 16 to conclude that the number of edges
from $A_{T}$ to the string $w^{(i)\to b}$ is at most $2d$, for each $b$. We
can therefore say that the probability we subtract is bounded from above by:

$\frac{2dm(m+1)}{\binom{n}{t}(n-t)}\sum_{T\in\mathcal{P}(t)}\sum_{w\in
B_{T}}\Pr_{x\sim
p_{\overline{T}}}[x=w]=\frac{2dm(m+1)}{n-t}\cdot\Pr_{T,z}\big{[}z\in
B_{T}\big{]}.$

As a result we have

$\Pr_{(\pi,y)}\big{[}X_{i}=1\big{]}\geq\Bigg{(}\zeta^{\prime}\xi-\left(1+4m^{3}\right)\cdot\Pr_{T,z}\big{[}\rho(z)\text{
is }t\text{-contributing}\big{]}\Bigg{)}\cdot\frac{d}{(n-t)m}.$

To conclude the proof of Lemma 9 for Case 2, we set $\gamma=d$. Then we either
have

$\Pr_{T,z}\big{[}\rho(z)\text{ is
}t\text{-contributing}\big{]}\geq\frac{\zeta^{\prime}\xi}{8m^{3}},$

which implies that

$\mathbb{E}_{\rho\sim\mathcal{D}(t,p)}\left[\Big{\|}\mu\left(p_{|\rho}\right)\Big{\|}_{2}\right]\gtrsim\frac{\zeta^{\prime}\xi}{m^{3}}\cdot\frac{\sqrt{d}}{m^{\kappa+1}}\gtrsim\frac{\alpha}{m^{7.5}\cdot\log(1/\alpha)\log^{2}n\log^{2}(nm)\log^{2}(nm/\alpha)}.$

Or we have

$\mathbb{E}_{(\pi,y)}\left[\Big{\|}\mu\left(p_{|\rho(\pi,y)}\right)\Big{\|}_{2}\right]\gtrsim\frac{t+1}{m^{\kappa}}\cdot\frac{1}{\sqrt{d}}\cdot\frac{d\zeta^{\prime}\xi}{(n-t)m}\gtrsim\frac{t}{n}\cdot\frac{\alpha}{m^{4.5}\cdot\log(1/\alpha)\log^{2}n\log^{2}(nm)\log^{2}(nm/\alpha)}.$

This finishes the proof of Lemma 9.

##  5 Mean Testing over Hypergrids

1:Dimension $n$, $M=(m_{1},\ldots,m_{n})$ and sample access to a distribution
$p$ over $\mathbb{Z}_{M}$

2:Draw $N=O(m\log(mn))$ samples $x$ from $p$.

3:if any $i\in[n]$ and $a\in[m_{i}]$ satisfy ($\\#$ samples with $x_{i}=a$ is
$>{2N}/{m_{i}}$ or $<{N}/({2m_{i}})$) then

4: return reject

5:else

6: return accept

7:end if

Algorithm 2 $\textsc{CoarseTest}(n,M,p)$

1:Dimension $n$, $M=(m_{1},\ldots,m_{n})$, $\epsilon>0$ and sample access to a
distribution $p$ over $\mathbb{Z}_{M}$

2:CoarseTest$(n,M,p)$ and return reject if it returns reject

3:for all $k\in[m^{2}]$ do

4: Run MeanTester$(n,p^{(k)},\epsilon/2m)$ for $O(\log m)$ many times

5: return reject if the majority of calls return reject

6:end for

7:return accept

Algorithm 3 $\textsc{ProjectedTestMean}(n,M,\epsilon,p)$

ProjectedTestMean is presented as Algorithm 3. It uses a preprocessing
subroutine called CoarseTest which is presented as Algorithm 2. It also uses
MeanTester from [CCK+21]. To state the performance guarantee of MeanTester, we
note that the bias vector $\mu(p)$ of a distribution $p$ over $\\{-1,1\\}^{n}$
has the following simpler form:

$\mu_{i}(p):=\Pr_{x\sim p}\big{[}x_{i}=1\big{]}-\Pr_{x\sim
p}\big{[}x_{i}=-1\big{]}.$

######  Theorem 27 (MeanTester [CCK+21]).

There is an algorithm (MeanTester) which, given $n$, sample access to a
distribution $p$ over $\\{-1,1\\}^{n}$, and a parameter $\epsilon\in(0,1]$,
draws

$O\left(\max\left\\{\frac{1}{\epsilon^{2}\sqrt{n}},\frac{1}{\epsilon}\right\\}\right)$

many samples from $p$ and has the following performance guarantee:

  1. 1.

If $p$ is the uniform distribution, the algorithm outputs accept with
probability at least $2/3$; and

  2. 2.

If $p$ satisfies $\|\mu(p)\|_{2}\geq\epsilon$, the algorithm outputs reject
with probability at least $2/3$.

The main idea behind ProjectedTestMean is to reduce the mean testing of $p$
over $\mathbb{Z}_{M}$ to that of the following collection of $m^{2}$
distributions over $\\{-1,1\\}^{n}$.

######  Definition 28.

Fix an arbitrary ordering of pairs $(c,d)\in\mathbb{Z}_{m_{i}}^{2}$ for each
$i\in[n]$ (so that we can refer to them as the $k$-th pair,
$k=1,\ldots,m_{i}^{2}$). Let $p$ be a distribution over $\mathbb{Z}_{M}$.
Given any $k\in[m^{2}]$, we define a distribution $p^{(k)}$ over $\\{-1,1\\}$
as follows. For each $i\in[n]$, let $(c_{i},d_{i})$ be the
$\min(k,m_{i}^{2})$-th pair in $\mathbb{Z}_{m_{i}}^{2}$. To draw $z\sim
p^{(k)}$, we first draw $x\sim p$ and then set $z_{i}$ for each $i\in[n]$ to
be $1$ if $x_{i}=c_{i}$, $-1$ if $x_{i}=d_{i}$, and an independent and
uniformly random bit from $\\{-1,1\\}$ if $x_{i}\notin\\{c_{i},d_{i}\\}$.

We note that sample access to $p^{(k)}$ for any $k$ can be simulated easily,
sample by sample, using sample access to $p$. The following simple lemma helps
connects $\|\mu(p)\|_{2}^{2}$ with $\sum_{k}\|\mu(p^{(k)})\|_{2}^{2}$.

######  Lemma 29.

Suppose that $p$ satisfies

$\frac{1}{4m_{i}}\leq\Pr_{x\sim p}\big{[}x_{i}=a\big{]}\leq\frac{4}{m_{i}}$
(45)

for all $i\in[n]$ and $a\in\mathbb{Z}_{m_{i}}$. Then we have

$\sum_{k\in[m^{2}]}\left\|\mu(p^{(k)})\right\|_{2}^{2}\geq\frac{1}{4m^{2}}\cdot\big{\|}\mu(p)\big{\|}_{2}^{2}.$

###### Proof.

Note that every term in $\|\mu(p)\|_{2}^{2}$ appears at least once on the LHS,
except that it is multiplied by $|\Pr_{x\sim p}[x_{i}=c]+\Pr_{x\sim
p}[x_{i}=d]|^{2}$ for some $i\in[n]$ and $c,d\in\mathbb{Z}_{m_{i}}$. The
latter (without squaring) is at least $1/(2m_{i})\geq 1/(2m)$ given the
assumption, and the lemma follows. ∎

The assumption (45) of Lemma 29 can be easily checked by CoarseTest (Algorithm
2). The proof of its performance guarantee below is standard using the
Chernoff bound.

######  Lemma 30.

There is an algorithm (Algorithm 2: CoarseTest) which, given
$n,M=(m_{1},\ldots,m_{n})$, and sample access to a distribution $p$ over
$\mathbb{Z}_{M}$, draws $O(m\log(mn))$ samples $x\sim p$ and satisfies:

  1. 1.

If $p$ is the uniform distribution, the algorithm outputs accept with
probability at least $1-1/n$.

  2. 2.

If there exists an $i\in[n]$ and an $a\in\mathbb{Z}_{m_{i}}$ such that either

$\Pr_{x\sim
p}\left[x_{i}=a\right]<\frac{1}{4m_{i}}~{}~{}~{}\text{or}~{}~{}~{}\mathbb{P}_{x\sim
p}\left[x_{i}=a\right]>\frac{4}{m_{i}},$

then the algorithm outputs reject with probability at least $1-1/n$.

We are now ready to finish the proof of Theorem 7 on ProjectedTestMean:

###### Proof of Theorem 7.

The number of samples used by ProjectedTestMean is

$O\big{(}m\log(mn)\big{)}+O\big{(}m^{2}\log
m\big{)}\cdot\max\left(\frac{1}{\sqrt{n}}\cdot\frac{4m^{2}}{\epsilon^{2}},\frac{2m}{\epsilon}\right).$

When $p$ is the uniform distribution, it follows by Lemma 30 that it is
rejected by CoarseTest with probability $o_{n}(1)$. Given that $p^{(k)}$ is
uniform for every $k\in[m^{2}]$, by setting the constant hidden in the $O(\log
m)$ large enough, it follows from Theorem 27, Chernoff bound and a union bound
over all $k\in[m^{2}]$ that it is rejected by calls to MeanTester with
probability $o_{n}(1)$.

When $p$ satisfies $\|\mu(p)\|_{2}\geq\epsilon m\sqrt{n}$, we consider two
cases. If there exist $i\in[n]$ and $a\in\mathbb{Z}_{m_{i}}$ such that either
$\Pr_{x}[x_{i}=a]<1/(4m_{i})$ or $\Pr_{x}[x_{i}=a]>4/m_{i}$, then $p$ is
rejected by CoarseTest with probability at least $1-o_{n}(1)$. On the other
hand, if this is not the case, then by Lemma 29, there exists a $k\in[m^{2}]$
such that $\|\mu(p^{(k)})\|_{2}\geq\epsilon\sqrt{n}/(2m)$. It follows from
Theorem 27 and Chernoff bound that with probability at least $1-o_{n}(1)$, the
majority of calls to MeanTest reject $p^{(k)}$. ∎

##  6 Discussion and Open Problems

In this paper, we study uniformity testing over extended high-dimensional
domains $[m_{1}]\times\dots\times[m_{n}]$ under the subcube conditional query
model. In doing so, we prove a robust version Pisier’s inequality over
hypergrids, which is a result of independent interest. We give an algorithm
which makes $\tilde{O}(\text{poly}(m)\sqrt{n}/\epsilon^{2})$ queries to a
subcube conditional sampling oracle, where $m=\max_{i}m_{i}$. This algorithm
has nearly optimal sample complexity when $m$ is a constant. The algorithm is
a modification of the algorithm of [CCK+21], where additional steps are needed
in our setting to properly draw the connection to a subroutine performing mean
testing over the hypercube.

We now highlight several compelling open problems related to distribution
testing over extended high-dimensional domains
$[m_{1}]\times\dots\times[m_{n}]$.

Lower bounds: There is currently a lack of techniques for studying lower-
bounds in the subcube conditional query model setting. To the best of our
knowledge, all the known lower-bounds in the subcube conditional query model
setting are transferred over from lower-bounds in the standard sampling
setting. For example, the lower-bound for uniformity testing in the hypercube
setting from [CDKS16, DDK16, BC17] is a consequence of lower-bounds for
testing uniformity of product distributions. This lower-bound, which matches
the upper-bound given in [CCK+21] up to poly-logarithmic factors, utilizes the
fact that subcube conditional queries do not provide stronger access to
product distributions than standard samples do. In the hypergrid setting
considered in this paper, the best known lower-bound is also carried over from
the standard sampling setting.

Dependence on $m$: It remains an interesting question to pin down the
dependency on $m$ in the query complexity of uniformity testing of
distributions over hypergrids. In this paper, we did not optimize the
dependency on $m$. We imagine that, with some work, the exponent in the
dependency on $m$ could be brought down to around half of its current value
(for example, from $m^{21}$ to $m^{10}$, perhaps). It remains an interesting
open question to obtain tight dependence on $m$, and a more challenging open
question to obtain tight bounds on all three parameters $n$, $m$ and
$\epsilon$. Although $m^{21}$ may not be optimal, the polynomial dependence on
$m$ is a meaningful step in analyzing distribution testing over extended
domains. Our analysis demonstrates how to extend and modify techniques from
the hypercube domain, reveals new technical challenges, and develops new
technical lemmas like the extended Pisier’s inequality suitable for the
hypergrid domain.

Identity testing in high dimensions with subcube conditional queries: There is
no direct reduction from identity testing of product distributions or general
distributions to uniformity testing. While identity testing in high dimensions
has been explored under weaker oracle assumptions ([BCŠV22]), query complexity
bounds for identity testing in the subcube conditional setting are unknown.
This is true even for distributions over hypercubes.

## References

  * [ADK15] Jayadev Acharya, Constantinos Daskalakis, and Gautam Kamath.  Optimal testing for properties of distributions.  In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
  * [AJMR12] Pranjal Awasthi, Madhav Jha, Marco Molinaro, and Sofya Raskhodnikova.  Testing lipschitz functions on hypergrid domains.  volume 74, 01 2012.
  * [BC17] Rishiraj Bhattacharyya and Sourav Chakraborty.  Property testing of joint distributions using conditional samples, 2017\.
  * [BCS17] Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri.  A $o(d)\cdot\text{polylog}n$ monotonicity tester for boolean functions over the hypergrid $[n]^{d}$, 2017.
  * [BCŠV22] Antonio Blanca, Zongchen Chen, Daniel Štefankovič, and Eric Vigoda.  Identity testing for high-dimensional distributions via entropy tensorization, 2022.
  * [BFR+00] T. Batu, L. Fortnow, R. Rubinfeld, W.D. Smith, and P. White.  Testing that distributions are close.  In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 259–269, 2000.
  * [BFR+13] Tuğkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D. Smith, and Patrick White.  Testing closeness of discrete distributions.  J. ACM, 60(1), feb 2013.
  * [BGKV21] Arnab Bhattacharyya, Sutanu Gayen, Saravanan Kandasamy, and N. V. Vinodchandran.  Testing product distributions: A closer look, 2021.
  * [BLMT23] Guy Blanc, Jane Lange, Ali Malik, and Li-Yang Tan.  Lifting uniform learners via distributional decomposition, 2023.
  * [BM87] J. Bourgain and V.D. Milman.  New volume ratio properties for convex sym-metric bodies in irn.  Inventiones mathematicae, 88:319–340, 1987.
  * [BRY14] Eric Blais, Sofya Raskhodnikova, and Grigory Yaroslavtsev.  Lower bounds for testing properties of functions over hypergrid domains.  In 2014 IEEE 29th Conference on Computational Complexity (CCC), pages 309–320, 2014.
  * [CCK+21] Clement L. Canonne, Xi Chen, Gautam Kamath, Amit Levi, and Erik Waingarten.  Random restrictions of high dimensional distributions and uniformity testing with subcube conditioning.  In Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’21, page 321–336, USA, 2021. Society for Industrial and Applied Mathematics.
  * [CDKS16] Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart.  Testing bayesian networks.  CoRR, abs/1612.03156, 2016.
  * [CDVV14] Siu-On Chan, Ilias Diakonikolas, Gregory Valiant, and Paul Valiant.  Optimal algorithms for testing closeness of discrete distributions.  In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’14, page 1193–1203, USA, 2014. Society for Industrial and Applied Mathematics.
  * [CFGM13] Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, and Arie Matsliah.  On the power of conditional samples in distribution testing.  In Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, ITCS ’13, page 561–580, New York, NY, USA, 2013\. Association for Computing Machinery.
  * [CFGM16] Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, and Arie Matsliah.  On the power of conditional samples in distribution testing.  SIAM Journal on Computing, 45(4):1261–1296, 2016.
  * [CGS+21] Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, Ameya Velingker, and Santhoshini Velusamy.  Linear space streaming lower bounds for approximating csps, 2021.
  * [CJLW20] Xi Chen, Rajesh Jayaram, Amit Levi, and Erik Waingarten.  Learning and testing junta distributions with subcube conditioning.  CoRR, abs/2004.12496, 2020.
  * [CRS12] Clement Canonne, Dana Ron, and Rocco A. Servedio.  Testing probability distributions using conditional samples, 2012.
  * [CRS14] Clément Canonne, Dana Ron, and Rocco A. Servedio.  Testing equivalence between distributions using conditional samples.  In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’14, page 1174–1192, USA, 2014. Society for Industrial and Applied Mathematics.
  * [CS12] Deeparnab Chakrabarty and C. Seshadhri.  Optimal bounds for monotonicity and lipschitz testing over the hypercube.  CoRR, abs/1204.0849, 2012.
  * [CS13] Deeparnab Chakrabarty and C. Seshadhri.  An optimal lower bound for monotonicity testing over hypergrids.  CoRR, abs/1304.5264, 2013.
  * [DDK16] Constantinos Daskalakis, Nishanth Dikkala, and Gautam Kamath.  Testing ising models.  CoRR, abs/1612.03147, 2016.
  * [DK16] Ilias Diakonikolas and Daniel M. Kane.  A new approach for testing properties of discrete distributions.  CoRR, abs/1601.05557, 2016.
  * [DKN14] Ilias Diakonikolas, Daniel M. Kane, and Vladimir Nikishkin.  Testing identity of structured distributions.  CoRR, abs/1410.2266, 2014.
  * [GR11] Oded Goldreich and Dana Ron.  On Testing Expansion in Bounded-Degree Graphs, page 68–75.  Springer-Verlag, Berlin, Heidelberg, 2011.
  * [HY20] Nathaniel Harms and Yuichi Yoshida.  Downsampling for testing and learning in product distributions, 2020.
  * [KMS18] Subhash Khot, Dor Minzer, and Muli Safra.  On monotonicity testing and boolean isoperimetric-type theorems.  SIAM Journal on Computing, 47(6):2238–2276, 2018.
  * [NS02] Assaf Naor and Gideon Schechtman.  Remarks on non linear type and pisier’s inequality.  Journal fur die Reine und Angewandte Mathematik, (552):213–236, 2002.
  * [O’D21] Ryan O’Donnell.  Analysis of boolean functions, 2021.
  * [Pan08] L. Paninski.  A coincidence-based test for uniformity given very sparsely sampled discrete data.  IEEE Trans. Inf. Theor., 54(10):4750–4755, oct 2008.
  * [Pis06] Gilles Pisier.  Probabilistic Methods in the Geometry of Banach Spaces, volume 1206, pages 167–241.  11 2006.
  * [VV14] Gregory Valiant and Paul Valiant.  An automatic inequality prover and instance optimal identity testing.  In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 51–60, 2014.

##  Appendix A Additional Proofs

###### Proof of Lemma 5.

: Fix any subset $S\subseteq[n]$ of size $t$. Given
$u\in\bigtimes_{i\in\overline{S}}\mathbb{Z}_{m_{i}}$, we write
$p_{|\rho({S},u)}$ to denote the distribution supported on
$\smash{\bigtimes_{i\in{S}}\mathbb{Z}_{m_{i}}}$ given by drawing $x\sim p$
conditioned on $x_{\overline{{S}}}=u$.

We expand the definition of total variation distance to obtain the following
expressions:

$\displaystyle 2d_{TV}(p,\mathcal{U})$
$\displaystyle=\sum_{x\in\mathbb{Z}_{M}}\left|p(x)-\prod_{i\in[n]}\frac{1}{m_{i}}\right|$
$\displaystyle=\sum_{u\in\bigtimes_{i\in\overline{S}}\mathbb{Z}_{m_{i}}}\sum_{v\in\bigtimes_{i\in
S}\mathbb{Z}_{m_{i}}}\left\lvert\Pr_{x\sim p}\big{[}x_{\overline{{S}}}=u\land
x_{{S}}=v\big{]}-\prod_{i\in[n]}\frac{1}{m_{i}}\right\rvert$
$\displaystyle=\sum_{u\in\bigtimes_{i\in\overline{{S}}}\mathbb{Z}_{m_{i}}}\sum_{v\in\bigtimes_{i\in{S}}\mathbb{Z}_{m_{i}}}\left\lvert
p_{\overline{S}}(u)\cdot\Pr_{x\sim
p}\big{[}x_{{S}}=v|x_{\overline{S}}=u\big{]}-\prod_{i\in[n]}\frac{1}{m_{i}}\right\rvert$
$\displaystyle\leq\sum_{u\in\bigtimes_{i\in\overline{{S}}}\mathbb{Z}_{m_{i}}}\sum_{v\in\bigtimes_{i\in{S}}\mathbb{Z}_{m_{i}}}\left\lvert
p_{\overline{{S}}}(u)\cdot\Pr_{x\sim
p}\big{[}x_{{S}}=v|x_{\overline{{S}}}=u\big{]}-p_{\overline{{S}}}(u)\cdot\prod_{i\in
S}\frac{1}{m_{i}}\right\rvert$ $\displaystyle\hskip 113.81102pt+\left\lvert
p_{\overline{{S}}}(u)\cdot\prod_{i\in
S}\frac{1}{m_{i}}-\left(\prod_{j\in\overline{{S}}}\frac{1}{m_{j}}\right)\cdot\left(\prod_{i\in
S}\frac{1}{m_{i}}\right)\right\rvert$
$\displaystyle=\sum_{u\in\bigtimes_{i\in\overline{{S}}}\mathbb{Z}_{m_{i}}}p_{\overline{{S}}}(u)\cdot
2d_{TV}(p_{|\rho(S,u)},\mathcal{U})+\sum_{v\in\bigtimes_{i\in{S}}\mathbb{Z}_{m_{i}}}\left(\prod_{i\in
S}\frac{1}{m_{i}}\right)\cdot 2d_{TV}(p_{\overline{{S}}},\mathcal{U})$
$\displaystyle=\sum_{u\in\bigtimes_{i\in\overline{{S}}}\mathbb{Z}_{m_{i}}}p_{\overline{{S}}}(u)\cdot
2d_{TV}(p_{|\rho({S},u)},\mathcal{U})+2d_{TV}(p_{\overline{{S}}},\mathcal{U}).$

Take the expectation of this inequality over the choice of
${S}\sim{S}_{\sigma}$. We obtain the lemma. ∎

###### Proof of Theorem 6 assuming Lemma 9.

The proof is the same as [CCK+21] except for a minor change. If $\sigma
n\not\in[5,n-5]$, then Theorem 6 is trivially satisfied. Consider $5\leq\sigma
n\leq n-5$ and let $\delta=\min(\sigma,1-\sigma)/2>0$. For notational
simplicity, for each $t\in[n-1]$, we write:

$\alpha_{t}:=\mathbb{E}_{T\sim\mathcal{S}(t)}\big{[}d_{TV}(p_{\overline{T}},\mathcal{U})\big{]}.$

Note that we can sample $\rho\sim\mathcal{D}_{\sigma}(p)$ by drawing
$k\sim\text{Bin}(n,\sigma)$ and $\rho\sim\mathcal{D}(k,p)$. Let $\beta_{t}$ be
the probability that $k=t$, for $k\sim\text{Bin}(n,\sigma)$. Let

$B:=\big{\\{}t\in[n-1]:t/n\in[\sigma-\delta,\sigma+\delta]\big{\\}}.$

Using a Chernoff bound, we see that $\sum_{t\in B}\beta_{t}\geq 1-2e^{-\delta
n/5}$. Therefore:

$\sum_{t\in
B}\beta_{t}\cdot\alpha_{t}\geq\mathbb{E}_{T\sim\mathcal{S}_{\sigma}}\big{[}d_{TV}(p_{\overline{T}},\mathcal{U})\big{]}-2e^{-\delta
n/5}.$ (46)

We then can derive the following series of inequalities:

$\displaystyle 2\cdot$
$\displaystyle\mathbb{E}_{\rho\sim\mathcal{D}_{\sigma}(p)}\left[\left\|\mu(p_{|\rho})\right\|_{2}\right]$
$\displaystyle\geq\sum_{t\in
B}\Big{(}\beta_{t}\cdot\mathbb{E}_{\rho\sim\mathcal{D}(t,p)}\left[\left\|\mu(p_{|\rho})\right\|_{2}\right]+\beta_{t+1}\cdot\mathbb{E}_{\rho\sim\mathcal{D}(t,p)}\left[\left\|\mu(p_{|\rho})\right\|_{2}\right]\Big{)}$
$\displaystyle\gtrsim\sum_{t\in
B}\beta_{t}\Big{(}\mathbb{E}_{\rho\sim\mathcal{D}(t,p)}\left[\left\|\mu(p_{|\rho})\right\|_{2}\right]+\mathbb{E}_{\rho\sim\mathcal{D}(t,p)}\left[\left\|\mu(p_{|\rho})\right\|_{2}\right]\Big{)}$
(47) $\displaystyle\gtrsim\frac{\sigma}{m^{7.5}\log^{4}(nm)}\cdot\sum_{t\in
B}\beta_{t}\cdot\frac{\alpha_{t}}{\log^{2}(nm/\alpha_{t})\log(1/\alpha_{t})}$
(48)
$\displaystyle\gtrsim\frac{\sigma}{m^{7.5}\text{poly}(\log(nm))}\cdot\widetilde{\Omega}\left(\mathbb{E}_{S\sim\mathcal{S}_{\sigma}}\left[d_{TV}(p_{\overline{S}},\mathcal{U})\right]-2e^{-\min(\sigma,1-\sigma)n/10}\right).$
(49)

To obtain (47), we used $t/n\in[\sigma-\delta,\sigma+\delta]$,
$\delta=\min(\sigma,1-\sigma)/2$ and $\sigma\geq 5/n$. This gives us:

$\frac{\beta_{t+1}}{\beta_{t}}=\frac{n-t}{t+1}\cdot\frac{\sigma}{1-\sigma}\geq\frac{(1-\sigma)/2}{(3\sigma/2)+(1/n)}\cdot\frac{\sigma}{1-\sigma}\gtrsim
1.$

To obtain (48) we apply Lemma 9 on each $t\in B$. For (49) we apply Jensen’s
inequality (as the function $f(a)=a/(\log^{2}(nm/a)\log(1/a))$ when $a\neq 0$
and $f(0)=0$ is convex in $[0,1]$) and use (46).

We can now conclude that Theorem 6 holds, assuming Lemma 9. ∎

###### Proof of Theorem 1.

Proof of (i) (completeness): For the completeness proof, we prove by induction
on $n$ that, when $p$ is uniform, SubCondUni$(n,M,\epsilon,p)$ returns accept
with probability at least $2/3$. For the base case when $n=1$, since (6) is
violated, we just run an algorithm (Lemma 4.20) from [BCŠV22], and the
completeness of the base case comes from the completeness of this algorithm.

Inductively, assume that the statement holds for dimensions $1$ through $n-1$.
If (6) is violated, then the analysis is trivial. For the case when (6) is
satisfied, we note that the restriction $p_{|\rho}$ is uniform for any $\rho$.
Since the total number of restrictions $\rho$ drawn in line 8 is
$\smash{O(L\log L)=\tilde{O}(m^{8.5}\sqrt{n}/\epsilon^{2})}$, we may set the
constant hidden in the choice of $r$ in line 10 to be sufficiently large so
that line 11 returns reject with probability no larger than $1/6$. Using the
inductive hypothesis, we can also say that SubCondUni rejects in line 19 with
probability no larger than $1/6$. The induction step follows from a union
bound.

Proof of (ii) (soundness): Assume that $d_{TV}(p,\mathcal{U})\geq\epsilon$. We
prove by induction on $n$ that SubCondUni rejects with probability at least
$2/3$. For the general case of the induction step, we know that either the
first case of (8) holds and thus, (9) holds, or the second case of (8) holds.

For the first case when (9) holds, we recall the choice of $L$ and notice that
the LHS of (9) is the expectation of a random variable with values in $[0,1]$
while the RHS is $1/L$. Using a bucketing argument, we find that there exists
a $j\in[\lceil\log(2L)\rceil]$ such that

$\Pr_{\rho\sim\mathcal{D}_{\sigma}(p)}\left[\frac{\left\|\mu(p_{|\rho})\right\|_{2}}{m\sqrt{n}}\geq\frac{1}{2^{j}}\right]\geq\frac{2^{j-1}}{L\lceil\log(2L)\rceil}\geq\frac{2^{j}}{4L\log(2L)}.$

So, for one of the restrictions $\rho\sim\mathcal{D}_{\sigma}(p)$ that we
sample, the condition in the event above holds, with probability at least
$1-e^{-2}>5/6$. When this holds, each of the calls to ProjectedTestMean on
line 10 rejects with probability at least $2/3$. So on line 11, SubCondUni
rejects with probability at least $2/3$.

For the second case, using bucketing again, there exists a
$j\in[\lceil\log(4/\epsilon)\rceil]$ such that

$\text{Pr}_{\rho\sim\mathcal{D}_{\sigma}(p)}\left[d_{TV}(p_{|\rho},\mathcal{U})\geq
2^{-j}\right]\geq\frac{\epsilon
2^{j}}{4\lceil\log(4/\epsilon)\rceil}\geq\frac{\epsilon
2^{j}}{8\log(4/\epsilon)}.$

Using (6) and Chernoff bound, the probability of $|\text{stars}(\rho)|>2\sigma
n$ is at most $e^{-\sigma n/3}<(\epsilon/8)^{3}$. Therefore,

$\text{Pr}_{\rho\sim\mathcal{D}_{\sigma}(p)}\left[d_{TV}(p_{|\rho},\mathcal{U})\geq
2^{-j}\text{ and }0<|\text{stars}(\rho)|\leq 2\sigma
n\right]\geq\frac{\epsilon 2^{j}}{16\log(4/\epsilon)}.$

Since we set $s_{j}^{\prime}=(32/\epsilon)\log(4/\epsilon)\cdot 2^{-j}$, the
probability that at least one restriction $\rho$ satisfies the condition above
is at least $5/6$. The probability that majority of the calls to
ProjectedTestMean reject this $\rho$ is also at least $5/6$. Therefore,
SubCondUni rejects with probability at least $2/3$.

Query complexity. Let $\Phi(n,m,\epsilon)$ denote its query complexity. Using
induction on $n$, we will show that

$\Phi(n,\epsilon)\leq
C\cdot\frac{m^{21}\sqrt{n}}{\epsilon^{2}}\cdot\log^{c}\left(\frac{nm}{\epsilon}\right)$
(50)

for some absolute constants $C,c>0$. Pick $C_{1}$ and $c_{1}$ to be two
constants such that upon running the algorithm from Lemma 4.20 of [BCŠV22] on
$n,m,\epsilon$ that violate (6), the query complexity is at most

$C_{1}\cdot\frac{\sqrt{m}}{\epsilon^{2}}\cdot\log^{c_{1}}\left(\frac{1}{\epsilon}\right).$

Let $C_{2}$ and $c_{2}$ be constants such that the complexity of the non-
recursive componen of SubCondUni (line 7 to line 13) is bounded by:

$C_{2}\cdot\frac{m^{21}\sqrt{n}}{\epsilon^{2}}\cdot\log^{c_{2}}\left(\frac{nm}{\epsilon}\right).$

Recall that $L=\tilde{O}({m^{8.5}\sqrt{n}}/\epsilon)$. The expression above
follows from the following calculation:

$\sum_{j=1}^{\lceil\log(2L)\rceil}\frac{L\log
L}{2^{j}}\cdot\left(O\big{(}m^{4}\log(mn)\big{)}\cdot\max\left\\{\frac{2^{2j}}{\sqrt{n}},2^{j}\right\\}.\right)\cdot\log\left(\frac{nm}{\epsilon}\right)=\tilde{O}\left(\frac{m^{21}\sqrt{n}}{\epsilon}\right).$

Finally, set $C:=2\max(C_{1},C_{2})$ and $c:=\max(c_{1},c_{2})$. We are now
ready to prove (50). The base case of $n=1$ is trivial. In the inductive step
the case when (6) is violated is also trivial. For the general case, with our
chosen $C$ and $c$, we have the following bound:

$\Phi(n,\epsilon)\leq\frac{C}{2}\cdot\frac{m^{21}\sqrt{n}}{\epsilon^{2}}\cdot\log^{c}\left(\frac{nm}{\epsilon}\right)+\sum_{j=1}^{\lceil\log(4/\epsilon)\rceil}s_{j}^{\prime}\cdot
100\log\left(\frac{16}{\epsilon}\right)\cdot\Phi(2\sigma n,2^{-j}).$

By the inductive hypothesis and the choice of $\sigma$, we can write each term
in the second sum as:

$C\cdot\frac{32}{\epsilon}\cdot\log\left(\frac{4}{\epsilon}\right)\cdot
100\log\left(\frac{16}{\epsilon}\right)\cdot m^{21}\sqrt{2\sigma n}\cdot
2^{j}\cdot\log^{c}\left(\sigma
nm2^{j+1}\right)\leq\frac{C}{32}\cdot\frac{m^{21}\sqrt{n}}{\epsilon}\cdot
2^{j}\cdot\log^{c}\left(\frac{nm}{\epsilon}\right)$

using $C_{0}\geq(32^{2}\cdot 100)^{2}\cdot 2$ (from the choice of $\sigma$ in
(5)). Lastly, use the following inequality:

$\sum_{j=1}^{\lceil\log(4/\epsilon)\rceil}2^{j}<2^{\lceil\log(4/\epsilon)\rceil+1}\leq\frac{16}{\epsilon}.$

By induction, we have now proven the query complexity. ∎