Proof. We first show that if the instance is not satisfiable then the algorithm declares the instance unsatisfiable and halts. For the sake of contradiction assume that this is not the case and \((V,C)\) returns a tree \(T\). Let \((u,v,w)\in C\) be a constraint violated by \(T\). Consider the point where vertices \(u\), \(v\) and \(w\) were separated. We know that \((u,v,w)\in C\) so it must have been the case that there was an edge connecting \(u\) and \(v\) with label \(w\), meaning that \(u\) and \(v\) must have been in the same part of the partition and \(w\) in the other. This results in the constraint being satisfied which in turn leads to a contradiction. We now turn our attention to the case where the instance is satisfiable and assume, for the sake of contradiction, that \((V,C)\) fails to find a tree satisfying all triplet constraints. Let \(T^*\) be a tree satisfying all the constraints and let \(S_f\) be the set of variables that cause the algorithm to fail, meaning that when the algorithm was considering the corresponding constraint graph \(G_f\), \(G_f\) was connected. Consider the lowest common ancestor, \(u\), of all the variables \(S_f\) in \(T^*\). Notice that the left and right subtrees of node \(u\) induce a non-trivial partitioning of \(S_f\); we view this partitioning as a cut \((S_1,S_2)\) for graph \(G_f\). Recall that \(G_f\) is connected, meaning that there is at least one edge crossing the cut. Let \((u,v,w)\) be the constraint that this edge corresponds to with \(u\in S_1\), \(v\in S_2\) and \(w\in S_f\). Notice that \(w\) must either be in \(S_1\) or \(S_2\); in both cases the constraint \((u,v,w)\) is violated, leading to a contradiction. ◻

Proof of Lemma 8. We first prove these results for random instances \(\mathcal{I}'_f\) and \(\mathcal{I}''_f\) drawn from the random model \(\mathcal{I}_f(n, p)\), in which each constraint is included independently with probability \(p = m / n^k\). Specifically, we show how to certify that \[\label{eq:max-total-val} \max_{\xi:[n]\to \Sigma} \Big( \operatorname{TotalVal}(\xi,\mathcal{I}'_f) - \operatorname{TotalVal}(\xi,\mathcal{I}''_f) \Big) \leq \epsilon m,\tag{9}\] where \(\operatorname{TotalVal}(\xi,\mathcal{I}'_f)\) and \(\operatorname{TotalVal}(\xi,\mathcal{I}''_f)\) denote the total (rather than average) payoffs of the solution \(\xi\) on the instances \(\mathcal{I}'_f\) and \(\mathcal{I}''_f\), respectively. The instances \(\mathcal{I}'_f\) and \(\mathcal{I}''_f\) are drawn independently from the \(\mathcal{I}_f(n,p)\) model. To simplify the exposition, we allow constraints \((x_1,\dots,x_k)\) to include repeated variables. Since the fraction of such constraints is negligible, this does not affect the value of the random CSP. We assume that every payoff function evaluates to \(1\) on any constraint with repeated variables. We also suppose that the parameter \(p\) is known to the algorithm. We then use a standard argument to show that the same result holds for the desired models \(\mathcal{I}_f(n, m)\) and \(\mathcal{I}_f(n, p)\) with unknown \(p\).

We write a polynomial integer program to bound the left-hand side of 9 . For every variable \(x_i\) and every possible value \(a \in \Sigma\), we introduce a decision variable \(y_{i,a} \in \{0,1\}\). Each assignment \(\xi: [n] \to \Sigma\) corresponds to an integer solution \(y\) defined as follows: \[y_{i,a} = \begin{cases} 1, & \text{if } \xi(i) = a, \\ 0, & \text{otherwise}. \end{cases}\]

We define the following polynomial objective function: \[\begin{gather} P(y) = \sum_{(x_1,\dots,x_k) \in \mathcal{C}'} \sum_{(a_1,\dots,a_k) \in \Sigma^k} f(a_1,\dots,a_k) \prod_{j=1}^{k} y_{x_j,a_j} \\ - \sum_{(x_1,\dots,x_k) \in \mathcal{C}''} \sum_{(a_1,\dots,a_k) \in \Sigma^k} f(a_1,\dots,a_k) \prod_{j=1}^{k} y_{x_j,a_j}. \end{gather}\]

Observe that the values of the solution \(\xi\) on the CSP instances \(\mathcal{I}'_f\) and \(\mathcal{I}''_f\) (i.e., \(\operatorname{TotalVal}(\xi,\mathcal{I}')\) and \(\operatorname{TotalVal}(\xi,\mathcal{I}'')\)) are equal to the first and second terms of \(P(y)\), respectively, for \(y\) defined as above. This equality holds because the product \(\prod_{j=1}^{k} y_{x_j,a_j}\) equals \(1\) if \(\xi(x_j) = a_j\) for all \(j\), and \(0\) otherwise. Consequently, \[f(\xi(x_1),\dots,\xi(x_k)) = \sum_{(a_1,\dots,a_k) \in \Sigma^k} f(a_1,\dots,a_k) \prod_{j=1}^{k} y_{x_j,a_j}.\]

We do not impose any additional constraints in the polynomial integer program (such as \(\sum_a y_{i,a} = 1\)), making it a relaxation of the exact optimization problem in the left-hand side of 9 . We further relax the integrality condition \(y_{i,a} \in \{0,1\}\) to allow \(y_{i,a} \in [-1,1]\). This yields a continuous relaxation of the original task of maximizing \(\operatorname{TotalVal}(\xi,\mathcal{I}'_f) - \operatorname{TotalVal}(\xi,\mathcal{I}''_f)\) over assignments \(\xi : [n] \to \Sigma\).

We certify that \(P(y) \leq \epsilon m\) for all \(y_{i,a} \in [-1,1]\) using Theorem 13, which in turn implies inequality 9 . To this end, we define \(|\Sigma|^k=q^k\) polynomials \(P_{a_1,\dots,a_k}\) for all \((a_1,\dots,a_k) \in \Sigma^k\): \[P_{a_1,\dots,a_k}(y) = \sum_{(x_1,\dots,x_k) \in \mathcal{C}'} \prod_{j=1}^{k} y_{x_j,a_j} - \sum_{(x_1,\dots,x_k) \in \mathcal{C}''} \prod_{j=1}^{k} y_{x_j,a_j},\] where \(\mathcal{C}'\) and \(\mathcal{C}''\) are the sets of constraints for instances \(\mathcal{I}'\) and \(\mathcal{I}''\). Then, \[P(y) = \sum_{(a_1,\dots,a_k)\in \Sigma^k} P_{a_1,\dots,a_k}(y)f(a_1,\dots,a_k).\] The coefficients of each polynomial \(P_{a_1,\dots,a_k}\) are random variables determined by the choice of the constraints in \(\mathcal{I}'_f\) and \(\mathcal{I}''_f\).

Let us verify the conditions of Theorem 13 for every polynomial \(P_{a_1,\dots,a_k}\). All coefficients are equal to \(1\), \(-1\), or \(0\) and are thus upper bounded by \(1\) in absolute value. Moreover, the coefficient of the monomial \(\prod y_{x_j,a_j}\) is \(1\) if \((x_1,\dots,x_k) \in \mathcal{C}' \setminus \mathcal{C}''\), \(-1\) if \((x_1,\dots,x_k) \in \mathcal{C}'' \setminus \mathcal{C}'\), and \(0\) otherwise. Thus, each coefficient takes the values \(-1\) and \(1\) with equal probability. Finally, the probability that a given coefficient is nonzero is \(2p(1 - p)\).

We run the algorithm from Theorem 13 to certify that each polynomial \(P_{a_1,\dots,a_k}(y)\) is upper bounded by \[2^{O(k)} \sqrt{2p} \, N^{3k/4} \log^{3/2} N,\] where \(N = |\Sigma| n\) is the number of variables \(y\).

The algorithm succeeds with high probability for each polynomial and, therefore, by the union bound, for all polynomials simultaneously (the number of polynomials is \(q^k\) where \(q\) and \(k\) are constants). Thus, we certify that \[P(y) \equiv \sum_{(a_1,\dots,a_k)\in \Sigma^k} P_{a_1,\dots,a_k}(y) f(a_1,\dots,a_k) \leq |\Sigma|^k 2^{O(k)} \sqrt{2p} \, N^{3k/4} \log^{3/2} (N).\] Using that \(p = m/n^k\), write \[|\Sigma|^k 2^{O(k)} \sqrt{2p} \, N^{3k/4} \log^{3/2} N \leq |\Sigma|^{O(k)} m^{1/2} n^{k/4} \log^{3/2} N.\] The right-hand side is upper bounded by \(\epsilon m\) for \(m > C_{\ref{lem:random-vs-random}}(q,k,\epsilon)n^{k/2} \log^{3} n\), where \(C_{\ref{lem:random-vs-random}}(q,k,\epsilon) = q^{O(k)}\epsilon^{-2}\) is some function of \(q\), \(k\), and \(\epsilon\).

II. We now prove Part II. We present a simple algorithm that certifies 8 with high probability over the choice of \(\mathcal{I}'_f\) and the internal randomness of the algorithm. In Appendix 6.2, we show how to obtain a deterministic algorithm by analyzing the proof of Theorem 13 from [2].

Let us first assume that \(p = K/L\), where \(K\) and \(L\) are integers upper bounded by \(\mathrm{poly}(n)\). We create \(L\) random instances \(\mathcal{I}^{(1)}_f, \dots, \mathcal{I}^{(L)}_f\) of the CSP as follows: for each tuple \((x_1, \dots, x_k) \in [n]^k\), we choose \(K\) random instances among the \(L\) instances and add the payoff function \(f\) on \((x_1, \dots, x_k)\) to each of them. Then, each instance \(\mathcal{I}^{(i)}_f\) is distributed according to \(\mathcal{I}_f(n, p)\). Note that the instances \(\mathcal{I}^{(1)}, \dots, \mathcal{I}^{(L)}\) are not independent. In fact, each tuple \((x_1, \dots, x_k) \in [n]^k\) appears in exactly \(K\) of them. Thus, for every \(\xi:[n]\to \Sigma\), we have \[\label{eq:expect-equals-empirical-avg} \mathbb{E}_{\mathcal{I}''_f} \big[\mathop{\mathrm{val}}(\xi,\mathcal{I}''_{f}) \big] = \frac{1}{L} \sum_{i=1}^L \mathop{\mathrm{val}}(\xi,\mathcal{I}^{(i)}).\tag{10}\] Now, for each \(i\), we certify that \[\label{eq:lem:random-vs-random-3} \max_{\xi: [n] \to \Sigma} \left( \mathop{\mathrm{val}}(\xi,\mathcal{I}'_f) - \mathop{\mathrm{val}}(\xi,\mathcal{I}^{(i)}_f) \right) \leq \epsilon/2\tag{11}\] using Part I. For each instance \(\mathcal{I}^{(i)}_f\), the certification succeeds with high probability. Thus, the expected number of failures is \(o(1) \cdot L\), and by Markov’s inequality, we successfully certify 11 for a \((1 - \epsilon/2)\) fraction of the \(L\) instances with high probability. In this case, we are guaranteed that the desired bound 8 holds, since by 10 we have \[\begin{gather} \max_{\xi: [n]\to \Sigma} \big( \mathop{\mathrm{val}}(\xi,\mathcal{I}'_{f}) - \mathbb{E}_{\mathcal{I}''_f} \big[\mathop{\mathrm{val}}(\xi,\mathcal{I}''_{f}) \big] \big) = \max_{\xi: [n] \to \Sigma} \left( \mathop{\mathrm{val}}(\xi,\mathcal{I}'_f) - \frac{1}{L}\sum_{i=1}^L\mathop{\mathrm{val}}(\xi,\mathcal{I}^{(i)}_f) \right) \leq\\ \leq \frac{1}{L}\sum_{i=1}^L \max_{\xi: [n] \to \Sigma} \underbrace{ \left( \mathop{\mathrm{val}}(\xi,\mathcal{I}'_f) - \mathop{\mathrm{val}}(\xi,\mathcal{I}^{(i)}_f) \right)}_{\Delta_i} \leq \epsilon/2 + \epsilon/2 = \epsilon. \end{gather}\] Here we used that for at least a \((1-\epsilon/2)\) fraction of indices \(i\), we have \(\Delta_i \le \epsilon/2\), and for the remaining at most \(\epsilon/2\) fraction of indices, we trivially have \(\Delta_i \le 1\), since the value of any CSP is at most \(1\).

III. We now sketch an argument showing how to obtain the result for the \(\mathcal{I}_f(n,m)\) model from the one for the \(\mathcal{I}_f(n,p)\) model. Choose a small parameter \(\rho > 0\) and set \(p = (1 - \rho)m / n^k\). Then, a random instance drawn from the \(\mathcal{I}_f(n,p)\) model contains between \((1 - 2\rho)m\) and \(m\) constraints with high probability. Moreover, the distributions \(\mathcal{I}_f(n,m)\) and \(\mathcal{I}_f(n,p)\) can be coupled so that, with high probability, the instance \(\mathcal{I}_f(n,m)\) consists of all constraints of \(\mathcal{I}_f(n,p)\), followed by at most \(2\rho m\) additional constraints. Thus, it suffices to refute the instance \(\mathcal{I}_f(n,p)\). A minor complication is that the algorithm does not know in advance how many constraints are in \(\mathcal{I}_f(n,p)\). However, it can try all possible values \(m' \in [(1 - 2\rho)m,\, m]\). The same reasoning applies to the \(\mathcal{I}_f(n,p)\) model when \(p\) is unknown.

If \(p = (1 - \rho)m / n^k\) as above, and \(\rho\) is rational, then \(p\) is a rational number with both numerator and denominator polynomially bounded in \(n\). (Otherwise, we may approximate \(p\) by a rational number \(K / L\) on a sufficiently fine grid.) ◻

Proof of Theorem 12. By Lemma 17, if \(m/n\) exceeds a constant that depends on \(\epsilon\), then there exists \(q\) such that the following inequality holds for random instances \(\mathcal{I}_{f_{\mathrm{\textsf{phy}}}}(n,m)\): \[\max_{\xi \in \Xi_{\frac{16}{q}, q}} \mathbb{E}\left[ \mathop{\mathrm{val}}^+(\xi,\mathcal{I}_{f_{\mathrm{\textsf{phy}}}}(n,m)) \right] \leq \alpha^*(f_{\mathrm{\textsf{phy}}}) + \epsilon.\] Fix such a value of \(q\), and certify that \[\max_{\xi: [n] \to \Sigma} \left( \mathop{\mathrm{val}}^+(\xi,\mathcal{I}_{f}) - \mathbb{E}_{\mathcal{I}_{f_{\mathrm{\textsf{phy}}}}(n,m)} \left[\mathop{\mathrm{val}}^+(\xi,\mathcal{I}_{f_{\mathrm{\textsf{phy}}}}(n,m)) \right] \right) \leq \epsilon\] using Lemma 8 (Part II), for every coarse tree with \(q\) leaves. Here, \(\Sigma\) denotes the set of leaves of the coarse tree, and \(f = f^+_{\mathrm{\textsf{phy}}}\) is the payoff function associated with that coarse tree. With high probability, all certifications succeed, since the number of ordered full binary trees with \(q\) leaves is given by the \((q-1)\)st Catalan number and is upper bounded by \(4^{q}\); in particular, this bound does not depend on \(n\). As a result, we certify that \[\max_{\xi \in \Xi_{\frac{16}{q}, q}} \mathop{\mathrm{val}}^+(\xi,\mathcal{I}_{f}) \leq \alpha^*(f_{\mathrm{\textsf{phy}}}) + \epsilon.\] This yields the desired result because, by Lemma 7, the optimal value of every Phylogenetic CSP instance \(\mathcal{I}_{f_{\mathrm{\textsf{phy}}}}\) is upper bounded by \(\mathop{\mathrm{val}}^+(\xi,\mathcal{I}_{f_{\mathrm{\textsf{phy}}}})\) for some coarse solution \(\xi \in \Xi_{\frac{16}{q}, q}\). ◻

Proof. We certify that for every assignment \(\xi : [n] \to \Omega\), the following holds: for every subset of \(t\) distinct indices \(i_1, \dots, i_t\) and every choice of labels \(a_{i_1}, \dots, a_{i_t}\), we have \[\label{eq:eps-mu-independ} \left| \Pr(\xi(X_{i_1}) = a_{i_1}, \dots, \xi(X_{i_t}) = a_{i_t}) - \mu_{\xi}(a_{i_1}) \cdots \mu_{\xi}(a_{i_t}) \right| \leq \epsilon'\tag{14}\] for a sufficiently small \(\epsilon' > 0\) (to be specified later). We do so by running the certifying algorithm from Lemma 8 with the payoff function \(f(x_1,\dots,x_k) = \mathbf{1}\{x_{i_1} = a_{i_1}, \dots, x_{i_t} = a_{i_t}\}\) for every choice of distinct indices \((i_1, \dots, i_t)\) and labels \((a_1, \dots, a_t)\). Note that this payoff function depends only on the \(t\) variables \(x_{i_1}, \dots, x_{i_t}\), and therefore the algorithm can be applied as long as \(m \ge C_{\ref{lem:random-vs-random}}(q,k,\epsilon) n^{t/2} \log^{3} n\) (\(m \geq C_{\ref{lem:random-vs-random}}(k, \epsilon)\, n^{t/2}\) for even \(t\)) . Each run of the algorithm succeeds with high probability, so by the union bound over all such choices of indices and labels, all runs succeed with high probability.

Observe that if the random variables \(\xi(X_1), \dots, \xi(X_k)\) satisfied condition (14 ) with \(\epsilon' = 0\), then they would be \(t\)-wise \(\mu_{\xi}\)-independent. However, in our case, \(\epsilon' > 0\). We claim that, nevertheless, condition (14 ) implies that the distribution of \((\xi(X_1), \dots, \xi(X_k))\) is \(\epsilon\)-close (in total variation distance) to some \(t\)-wise \(\mu_{\xi}\)-independent distribution. For the uniform distribution \(\mu\) over the binary domain, this claim follows from the work of [62] (see also [63], [64]). For general (non-uniform) distributions \(\mu\) over larger domains, we prove Theorem 20 in Appendix 6.4.

To apply Theorem 20, we verify that its conditions hold. Let \(f : \Omega^k \to \mathbb{C}\) be an arbitrary function depending on at most \(t\) variables, say \(a_{i_1}, \dots, a_{i_t}\). Then \[\begin{gather} \Bigl| \sum_{(a_1, \dots, a_k) \in \Omega^k} \Big( \Pr(\xi(X_1) = a_1, \dots, \xi(X_k) = a_k) - \mu_{\xi}(a_1) \cdots \mu_{\xi}(a_k) \Big) f(a_1, \dots, a_k) \Bigr| = \\ = \Bigl| \sum_{(a_{i_1}, \dots, a_{i_t}) \in \Omega^t} \underbrace{\Big( \Pr(\xi(X_{i_1}) = a_{i_1}, \dots, \xi(X_{i_t}) = a_{i_t}) - \mu_{\xi}(a_{i_1}) \cdots \mu_{\xi}(a_{i_t}) \Big) f(a_1, \dots, a_k)}_{(*)} \Bigr|. \end{gather}\] Each expression \((*)\) is bounded in absolute value by \(\epsilon'\|f\|_{\infty}\), and there are \(q^t\) such terms. Thus, the entire expression is upper bounded by \(q^t \epsilon' \|f\|_\infty\).

Theorem 20 guarantees the existence of a \(t\)-wise \(\mu_{\xi}\)-independent distribution \(\mathcal{D}\) that is \(\epsilon\)-close in total variation distance to the distribution of \((\xi(X_1), \dots, \xi(X_k))\), where \(\epsilon = O\big((2q)^k (q^t \epsilon')^{1/(k+1)}\big)\). Choosing \(\epsilon'\) sufficiently small completes the proof. ◻

Proof of Theorem 16. As in the proof of Theorem 12, let \(q\) be a sufficiently large constant to be specified later. Let \((X_1,\dots,X_k)\) be a random constraint in \(\mathcal{C}\). Using the algorithm from Lemma 9, we certify that for every assignment \(\xi : [n] \to [q]\), there exists a \(t\)-wise distribution \(\mathcal{D}\) on \([q]^k\) that is \(\epsilon\)-close (in total variation distance) to the distribution of \((\xi(X_1),\dots,\xi(X_k))\). We show that if the certification algorithm succeeds (which happens with high probability), then the optimal value of the Phylogenetic CSP instance \(\mathcal{I}_{f_{\mathrm{\textsf{phy}}}}\) is at most \(\beta^*_t(f_{\mathrm{\textsf{phy}}}) + 2\epsilon\).

The value of any solution to \(\mathcal{I}_{f_{\mathrm{\textsf{phy}}}}\) is upper bounded by the value of a coarse solution, i.e., \(\mathop{\mathrm{val}}^+(\xi, \mathcal{I}_{f_{\mathrm{\textsf{phy}}}})\) for some \(\xi \in \Xi_{\frac{16}{q}, q}\). Let \(\xi^* \in \Xi_{\frac{16}{q}, q}\) be the assignment that maximizes this value. The assignment \(\xi^*\) maps variables in \([n]\) to the leaves of some tree, where each leaf is assigned a color, and at most a \(16/q\) fraction of variables are mapped to any single color class. For convenience, we associate each leaf with an element of \([q]\) and treat \(\xi^*\) as a function from \([n]\) to \([q]\). Then, by Lemma 9, there exists a \(t\)-wise \(\mu_{\xi^*}\)-independent distribution \(\mathcal{D}\) on \([q]^k\) that is \(\epsilon\)-close to the distribution of \((\xi^*(X_1), \dots, \xi^*(X_k))\). Therefore, \[\mathop{\mathrm{val}}^+(\xi^*, \mathcal{I}_{f_{\mathrm{\textsf{phy}}}}) = \mathbb{E}_{(X_1, \dots, X_k) \in \mathcal{C}}[f^+(\xi^*(X_1), \dots, \xi^*(X_k))] \leq \mathbb{E}_{(a_1, \dots, a_k) \sim \mathcal{D}}[f^+(a_1, \dots, a_k)] + \epsilon.\] Also, by the definition of \(\beta^*_t(f_{\mathrm{\textsf{phy}}})\), \[\mathbb{E}_{(a_1, \dots, a_k) \sim \mathcal{D}}[f^-(a_1, \dots, a_k)] \leq \beta^*_t(f_{\mathrm{\textsf{phy}}}).\] It remains to bound the difference: \[\mathbb{E}_{(a_1, \dots, a_k) \sim \mathcal{D}}[f^+(a_1, \dots, a_k) - f^-(a_1, \dots, a_k)] \leq \epsilon.\]

Note that \(f^+(a_1,\dots,a_k)\) and \(f^-(a_1,\dots,a_k)\) differ only when \(a_i\) and \(a_j\) share the same color for some distinct \(i,j \in \{1,\dots,k\}\). Since \(\xi^*\) maps at most a \(16/q\) fraction of variables to any single color, the marginal distribution \(\mu_{\xi^*}\) assigns at most \(16/q\) mass to each color class. Hence, the probability that \(\mathop{\mathrm{color}}(a_i) = \mathop{\mathrm{color}}(a_j)\) for some \(i \neq j\) is at most \(16/q \cdot \binom{k}{2} < 8k^2 / q\). Choosing \(q = 8k^2 / \epsilon\) ensures that this quantity is at most \(\epsilon\), completing the proof. ◻

Proof. First observe that \(P_a(y)\leq \sum_{i=1}^{N}W_i\). By Cauchy-Schwarz inequality, we have that: \[\begin{align} \mathbb{E}_{\mathcal{I}_f''}[P_a(y)]&\leq \mathbb{E}_{\mathcal{I}_f''}\left[\sum_{i=1}^{N}W_i\right]\\ &\leq \mathbb{E}_{\mathcal{I}_f''}\left[\sqrt{N}\sqrt{\sum_{i=1}^{N}W_i^2}\right]\\ &=\sqrt{N}\cdot \mathbb{E}_{\mathcal{I}_f''}\left[\sqrt{\sum_{i}^{N}W_i^2}\right] \end{align}\] By Jensen’s inequality, we get that: \[\begin{align} \mathbb{E}_{\mathcal{I}_f''}\left[\sqrt{\sum_{i=1}^{N}W_i^2}\right]\leq \sqrt{\mathbb{E}_{\mathcal{I}_f''}\left[\sum_{i=1}^{N}W_i^2\right]} \end{align}\] We now bound \(\mathbb{E}_{\mathcal{I}_f''}\left[\sum_{i=1}^{N}W_i^2\right]\). Observe that for \(A\) defined as in 15 , we have that: \[\begin{align} \sum_{i=1}^{N}W_i^2&=(y^{\otimes k-1})^{\top}Ay^{\otimes k-1}+\sum_{T,U\in [N]^{\frac{k-1}{2}}}\prod_{l\in T}y_l^2\prod_{j\in U}y_j^2\sum_{i=1}^{N}w(T,U,i)^2\\ &\leq (y^{\otimes k-1})^{\top}Ay^{\otimes k-1}+\sum_{T\in [N]^k}w(T)^2 \end{align}\] Applying expectations, we have that: \[\begin{align} \mathbb{E}_{\mathcal{I}_f''}\left[\sum_{i=1}^{N}W_i^2\right]&\leq \mathbb{E}_{\mathcal{I}_f''}\left[(y^{\otimes k-1})^{\top}Ay^{\otimes k-1}+\sum_{T\in [N]^k}w(T)^2\right]\\ &=(y^{\otimes k-1})^{\top}\mathbb{E}_{\mathcal{I}_f''}\left[A\right]y^{\otimes k-1}+\mathbb{E}_{\mathcal{I}_f''}\left[\sum_{T\in[N]^k}w(T)^2\right]\\ &\leq N^{k-1}\|\mathbb{E}_{\mathcal{I}_f''}\left[A\right]\|+\mathbb{E}_{\mathcal{I}_f''}\left[\sum_{T\in[N]^k}w(T)^2\right] \end{align}\] Where from the second to the third line we use that \(y\in[-1,1]^{N}\), meaning that \(\|y^{\otimes k-1}\|\leq N^{\frac{k-1}{2}}\). The claim of the lemma follows. ◻

Proof. We first prove (I). For convenience, we let \(B=2^{O(k)}pN^{k/2}\log^3(N)\). We use the following lemma from [2].

Notice that the conditions of Lemma 12 hold in our case, so we get the bound on \(\mathbb{E}[\mathop{\mathrm{tr}}((AA^{\top})^r)]\). By applying Jensen’s inequality twice, we get that: \[\begin{align} \Pr\big(\|\mathbb{E}_{\mathcal{I}_{f}''}[A]\|\geq B\big)&\leq \Pr\big(\mathbb{E}_{\mathcal{I}_{f}''}[\|A\|]\geq B\big)\\ &= \Pr\big(\left(\mathbb{E}_{\mathcal{I}_{f}''}[\|A\|]\right)^{2r}\geq B^{2r}\big)\\ &\leq \Pr\big(\mathbb{E}_{\mathcal{I}_{f}''}[\|A\|^{2r}]\geq B^{2r}\big) \end{align}\] We now use that \(\|A\|^{2r}\leq \mathop{\mathrm{tr}}\left((AA^{\top})^{r}\right)\), to get that: \[\begin{align} \Pr\big(\mathbb{E}_{\mathcal{I}_{f}''}[\|A\|^{2r}]\geq B^{2r}\big)\leq \Pr\big(\mathbb{E}_{\mathcal{I}_f''}\left[\mathop{\mathrm{tr}}\left((AA^{\top})^r\right)\right]\geq B^{2r}\big) \end{align}\] Applying Markov’s inequality, we get that: \[\begin{align} \Pr\big(\|\mathbb{E}_{\mathcal{I}_f''}[A]\|\geq B\big)&\leq\frac{\mathbb{E}\left[\mathbb{E}_{\mathcal{I}_f''}\left[\mathop{\mathrm{tr}}\left((AA^{\top})^{r}\right)\right]\right]}{B^{2r}}\\ &=\frac{\mathbb{E}\left[\mathop{\mathrm{tr}}\left((AA^{\top})^{r}\right)\right]}{B^{2r}}. \end{align}\] Taking \(r=\Theta(\log(N))\) yields (I). We now focus on (II). We have that: \[\begin{align} \mathbb{E}_{\mathcal{I}_f''}\left[\sum_{T\in [N]^{k}} w(T)^2\right]&=\sum_{T\in [N]^{k}}\mathbb{E}_{\mathcal{I}_f''}\left[w(T)^2\right]\\ &=\sum_{\substack{T\in [N]^k\\a(T)=a}}\mathbf{1}{\{x(T)\in \mathcal{I}_{f}'\}}+p-2p\mathbf{1}{\{x(T)\in \mathcal{I}_f'\}}\\ &\leq \sum_{\substack{T\in[N]^k\\a(T)=a}}\mathbf{1}{\{x(T)\in \mathcal{I}_f'\}}+p\\ &=pn^{k}+\sum_{\substack{T\in[N]^k\\a(T)=a}}\mathbf{1}{\{T\in \mathcal{I}_f'\}} \end{align}\] We now use the Chernoff bound for the sum \(\sum_{\substack{T\in[N]^k\\a(T)=a}}\mathbf{1}{\{T\in \mathcal{I}_f'\}}\), this is a sum of \(n^k\) independent Bernoulli random variables with parameter \(p\). By Theorem 4.4 in [55] we get that: \[\begin{align} \Pr\big(\sum_{\substack{T\in [N]^k\\a(T)=a}}\mathbf{1}{\{T\in \mathcal{I}_f'\}}\geq 2pn^k\big)\leq \exp\left(-\frac{4}{3}pn^k\right) \end{align}\] Part (II) of the lemma follows. ◻

Proof. For convenience, let \(P(x)=\sum_{i=1}^{m}w(T^{(i)})\prod_{j\in T}x_j\). We will relax the problem by introducing for every \(T\in [n]^{\frac{k}{2}}\) a vector \(U_{T}\), which in the intended solution is \(U_{T}=e\cdot \prod_{i\in T}x_i\) where \(e\) is a unit vector. We have that: \[\begin{align} P(x_1,\ldots,x_n)\leq \max_{\substack{U_T,\\ \|U_T\|\leq 1}}\sum_{i=1}^{m}w(T^{(i)})\langle U_{T^{(i)}_1}, U_{T^{(i)}_2}\rangle \end{align}\] The algorithm solves this semidefinite program that upper bounds \(P(x_1,\ldots,x_n)\) and certifies that it is indeed less that or equal to \(4K_G\sqrt{\frac{m}{n^k}}n^{\frac{3k}{4}}\). It remains to show that with high probability over the randomness in \(\{w(T^{(i)})\}_{i\in \{1,2,\ldots, m\}}\) the semidefinite program is bounded by \(4K_G\sqrt{\frac{m}{n^k}}n^{\frac{3k}{4}}\). To that end, we use Grothendieck’s inequality (see [65]–[67]) to get that: \[\begin{align} \max_{\substack{U_T,\\ \|U_T\|\leq 1}}\sum_{i=1}^{m}w(T^{(i)})\langle U_{T^{(i)}_1}, U_{T^{(i)}_2}\rangle \leq K_G\cdot \max_{Y,Z\in \{-1,1\}^{n^{k/2}}}\sum_{i=1}^{m}w(T^{(i)})Y_{T^{(i)}_1}Z_{T^{(i)}_2}. \end{align}\] We now fix \(Y,Z\) and use the Hoeffding bound (see e.g., Theorem 2.2.6 in [68]) to get that: \[\begin{align} \Pr\big(\sum_{i=1}^{m}w(T^{(i)})Y_{T_1^{(i)}}Z_{T_2^{(i)}}\geq 4\sqrt{\frac{m}{n^k}}n^{3k/4}\big)\leq \exp\left(-8n^{k/2}\right) \end{align}\] We apply the union bound over all \(Y,Z\) to get that: \[\begin{align} \Pr\big(\exists Y,Z: \sum_{i=1}^{m}w(T^{(i)})Y_{T_1^{(i)}}Z_{T_2^{(i)}}\geq 4\sqrt{\frac{m}{n^k}}n^{3k/4}\big)&\leq 2^{2n^{k/2}}\exp\left(-8n^{k/2}\right)\\ &\leq \exp\left(2n^{k/2}-8n^{k/2}\right)\\ &=\exp\left(-6n^{k/2}\right) \end{align}\] It follows that with probability at least \(1-\exp\left(-6n^{k/2}\right)\) it holds that: \[\begin{align} \max_{\substack{U_T,\\ \|U_T\|\leq 1}}\sum_{i=1}^{m}w(T^{(i)})\langle U_{T^{(i)}_1}, U_{T^{(i)}_2}\rangle \leq 4K_G\sqrt{\frac{m}{n^k}}n^{\frac{3k}{4}}. \end{align}\] The theorem follows. ◻

Proof. Let \(\mu^{\otimes k}\) be the product measure on \([q]^k\) defined as \(\mu^{\otimes k} (a_1,\dots,a_k) = \mu(a_1)\cdots \mu(a_k)\) and \(F(a_1,\dots,a_k) = \nu(a_1,\dots,a_k)-\mu^{\otimes k}(a_1,\dots,a_k)\). Consider the \(k\)-dimensional Discrete Fourier Transform of the function \(F\): \[\widehat{F}(b) = \sum_{a \in [q]^k} F(a) \cdot \overline{\chi_b(a)},\] where \(\chi_b(a) = e^{\frac{2\pi i \langle a, b \rangle}{q}}\) is the character associated with the frequency \(b = (b_1, \dots, b_k)\). The inverse transform is given by \[F(a) = \frac{1}{q^k} \sum_{b\in [q]^k} \widehat{F}(b) \cdot \chi_b(a).\]

Let \(B_t\) be the set of all vectors \(b = (b_1, \dots, b_k)\) in \([q]^k\) with at most \(t\) nonzero coordinates. Every character \(\chi_b(a_1, \dots, a_k)\) with \(b\) in \(B_t\) depends on at most \(t\) of the coordinates \(a_i\) (those for which \(b_i \neq 0\)). Also, \(\|\chi_b\|_{\infty} =\|\overline{\chi_b}\|_{\infty}=1\). Thus, by the assumption of Theorem 20, we have \[|\widehat{F}(b)| = \left| \sum_{a \in [q]^k} F(a) \cdot \overline{\chi_b(a)} \right| \leq \epsilon.\]

We now construct the measure \(\nu'\) by removing all Fourier frequencies from \(\nu\) corresponding to \(b \in B_t\) to make the measure \(t\)-wise \(\mu\)-independent, and by slightly rescaling the remaining Fourier coefficients to guarantee that \(\nu'\) is nonnegative. Specifically, define \[\nu'(a) = \mu^{\otimes k}(a) + \frac{(1 - \delta)}{q^k} \sum_{b \in [q]^k \setminus B_t} \widehat{F}(b)\, \chi_b(a),\] where \(\delta = \epsilon \gamma^{-k}|B_t|\). Note that \(\nu(a')\) is a real number for every \(a \in [q]^k\), because \(\widehat{F}(b) = \overline{\widehat{F}(-b)}\) and \(\chi_b(a) = \overline{\chi_{-b}(a)}\). Thus, the sum \(\widehat{F}(b)\chi_b(a) + \widehat{F}(-b)\chi_{-b}(a)\) is real. Here, \(-b\) denotes the coordinate-wise negation modulo \(q\). Also, observe that \[\widehat{F}(0) = \sum_{a\in[q]^k} F(a) = \nu([q]^k) - \mu^{\otimes k}([q]^k) = 1 - 1 =0.\]

We next verify that \(\nu'\) satisfies the conditions of Lemma 13. First, we check that \(\nu'\) is a probability measure; that is, \(\nu'([q]^k) = 1\) and \(\nu'\) is nonnegative. Since \(\sum_{a \in [q]^k} \chi_b(a) = 0\) for all \(b \neq 0\), we have \[\nu'([q]^k)\equiv \sum_{a \in [q]^k} \nu'(a) = \sum_{a \in [q]^k} \mu^{\otimes k}(a) \equiv \mu^{\otimes k}([q]^k)= 1.\] Now, using that \(\nu(a) = \mu^{\otimes k}(a) + F(a)\), we get \[\begin{align} \nu'(a) &= \mu^{\otimes k}(a) + (1-\delta) \Big(F(a) - \frac{1}{q^k} \sum_{b \in B_t} \widehat{F}(b)\, \chi_b(a) \Big) \\&= \delta\mu^{\otimes k}(a) + (1-\delta)\,\nu(a) - \frac{(1 - \delta)}{q^k} \sum_{b \in B_t} \widehat{F}(b)\, \chi_b(a) \\&\geq \delta\mu^{\otimes k}(a) - \frac{(1 - \delta)}{q^k} \sum_{b \in B_t} \widehat{F}(b)\, \chi_b(a). \end{align}\] Recall that \(\mu(z)\geq \gamma/q\) for all \(z\in[q]\) and hence \(\mu^{\otimes k}(a) \geq \gamma^k/q^k\). Therefore, \[\nu'(a) \geq \frac{1}{q^k} \Big[ \delta \gamma^k - (1 - \delta) \sum_{b \in B_t} \widehat{F}(b)\, \chi_b(a) \Big].\] Since each Fourier coefficient \(\widehat{F}(b)\) is bounded in absolute value by \(\epsilon\), \(|\chi_b(a)| = 1\), and \(\delta = \epsilon \gamma^{-k} |B_t|\), the right-hand side is at least \(\tfrac{1}{q^k}\Big[\epsilon |B_t| - (1 - \delta)\, \epsilon\, |B_t|\Big] > 0\). This proves that \(\nu'(a) > 0\) for all \(a\), and hence \(\nu'\) is a probability measure.

We now show that \(\nu'\) is \(t\)-wise \(\mu\)-independent, and then estimate \(d_{\mathrm{\textsf{TV}}}(\nu, \nu')\). Consider \(k\) random variables \((X_1, \dots, X_k)\) with joint distribution given by the measure \(\nu'\). We need to show that they are \(t\)-wise \(\mu\)-independent. That is, for every \(t\) indices \(i_1, \dots, i_t\) and values \(a^*_{i_1}, \dots, a^*_{i_t}\), we must have \[\Pr(X_{i_1} = a^*_{i_1}, \dots, X_{i_t} = a^*_{i_t}) = \mu(a^*_{i_1}) \cdots \mu(a^*_{i_t}).\] The probability above can be expressed as the expectation of the indicator function of the event \(\mathbf{1}\{a_{i_1} = a^*_{i_1}, \dots, a_{i_t} = a^*_{i_t}\}\): \[\Pr(X_{i_1} = a^*_{i_1}, \dots, X_{i_t} = a^*_{i_t}) = \sum_{a \in [q]^k} \mathbf{1}\{a_{i_1} = a^*_{i_1}, \dots, a_{i_t} = a^*_{i_t}\} \cdot \nu'(a).\] The indicator function \(\mathbf{1}\{a_{i_1} = a^*_{i_1}, \dots, a_{i_t} = a^*_{i_t}\}\) depends only on the \(t\) variables \(a_{i_1}, \dots, a_{i_t}\) and is therefore orthogonal to all characters \(\chi_b\) with \(b \notin B_t\). That is, \[\sum_{a \in [q]^k} \chi_b(a) \cdot \mathbf{1}\{a_{i_1} = a^*_{i_1}, \dots, a_{i_t} = a^*_{i_t}\} = 0.\] Hence, \[\begin{align} \sum_{a \in [q]^k} \mathbf{1}\{a_{i_1} = a^*_{i_1}, \dots, a_{i_t} = a^*_{i_t}\} \cdot \nu'(a) &= \sum_{a \in [q]^k} \mathbf{1}\{a_{i_1} = a^*_{i_1}, \dots, a_{i_t} = a^*_{i_t}\} \cdot \mu^{\otimes k}(a) \\ &= \mu^{\otimes k}(\{a \in [q]^k : a_{i_1} = a^*_{i_1}, \dots, a_{i_t} = a^*_{i_t}\})\\ &= \mu(a^*_{i_1}) \cdots \mu(a^*_{i_t}). \end{align}\]

We are almost done. It only remains to estimate \(d_{\mathrm{\textsf{TV}}}(\nu, \nu')\equiv \frac{1}{2} \|\nu - \nu'\|_1\). We have \[\begin{align} \nu(a) - \nu'(a) &= \Big(\mu^{\otimes k}(a) + F(a)\Big) - \Big( \mu^{\otimes k}(a) + \frac{(1 - \delta)}{q^k} \sum_{b \in [q]^k \setminus B_t} \widehat{F}(b)\, \chi_b(a) \Big)\\ &= F(a) - \frac{(1 - \delta)}{q^k} \sum_{b \in [q]^k \setminus B_t} \widehat{F}(b)\, \chi_b(a). \end{align}\] We write \(F(a) = \delta F(a) + (1 - \delta) F(a)\) and use the Fourier expansion of \((1 - \delta) F(a)\): \[\begin{align} \nu(a) - \nu'(a) &= \delta F(a) + \frac{(1 - \delta)}{q^k} \sum_{b \in [q]^k} \widehat{F}(b)\, \chi_b(a) - \frac{(1 - \delta)}{q^k} \sum_{b \in [q]^k \setminus B_t} \widehat{F}(b)\, \chi_b(a)\\ &= \delta F(a) + \frac{(1 - \delta)}{q^k} \sum_{b \in B_t} \widehat{F}(b)\, \chi_b(a). \end{align}\]

We now bound the \(\ell_1\) norm of the first term: \(\|\delta F\|_1 = \delta \|F\|_1 = \delta \|\nu - \mu^{\otimes k}\|_1 \leq 2\delta\). For the second term, we use that the \(\ell_1\) norm of each function \(\chi_b / q^k\) is \(1\), and that \(|\widehat{F}(b)| \leq \epsilon\) for all \(b \in B_t\). Thus, the \(\ell_1\) norm of each term \(\frac{(1 - \delta)}{q^k} \widehat{F}(b)\, \chi_b(a)\) is at most \((1 - \delta)\epsilon <\epsilon\). Therefore, the \(\ell_1\) norm of \(\nu-\nu'\) is upper bounded by \(\delta + |B_t|\epsilon = (\gamma^{-k} +1)|B_t|\epsilon\). We get (using that \(\gamma\leq 1\)) \[d_{\mathrm{\textsf{TV}}}(\nu, \nu') \equiv \frac{1}{2}\|\nu' - \nu\|_1 \leq |B_t|\gamma^{-k}\epsilon,\] Observing that \(|B_t| \leq \binom{k}{t} q^t\) concludes the proof. ◻

Proof of Theorem 20. We now extend the result to the general case, where \(\mu\) is not necessarily bounded away from zero. Let \(\gamma = \epsilon^{\frac{1}{k+1}}\). If \(\mu(z) \geq \gamma / q\) for all \(z \in [q]\), then Lemma 13 applies directly. Otherwise, there exists at least one \(z\) such that \(\mu(z) < \gamma / q\).

Without loss of generality, assume that \(\mu(0) \geq \mu(1) \geq \cdots \geq \mu(q - 1)\). If this is not the case, we may simply rearrange the elements of \([q]\). We apply Lemma 13 to an auxiliary measure \(\tilde{\mu}\) that satisfies the lower bound assumption of the lemma. We define \(\tilde{\mu}\) by coarsening the domain of \(\mu\) – merging all low-probability elements into a single one. Since \(\sum_{z=0}^{q-1} \mu(z) = 1\), there exists at least one \(z\) with \(\mu(z) \geq 1/q > \gamma/q\). Let \(\tilde{q}\) be the largest index such that \(\mu(z) \geq \gamma / q\) for all \(z \leq \tilde{q}\). For \(z > \tilde{q}\), we then have \(\mu(z) < \gamma / q\). Define \(\tilde{\mu}\) on \([\tilde{q} + 1]\) by preserving the high-probability elements and combining the rest: \[\tilde{\mu}(z) = \begin{cases} \mu(z), & \text{if } z < \tilde{q}; \\ \sum_{z' = \tilde{q}}^{q - 1} \mu(z'), & \text{if } z = \tilde{q}. \end{cases}\] Then \(\tilde{\mu}(z) \geq \gamma / q\) for all \(z \in [\tilde{q} + 1]\), and hence \(\tilde{\mu}(z) \geq \tilde{\gamma} / (\tilde{q} + 1)\), where \(\tilde{\gamma} = (\tilde{q} + 1) \gamma/ q\).

Let \((X_1, \dots, X_k)\) be random variables with joint distribution given by the measure \(\nu\). Define the modified random variables \((\tilde{X}_1, \dots, \tilde{X}_k)\) as follows: \[\tilde{X}_i = \begin{cases} X_i, & \text{if } X_i < \tilde{q}; \\ \tilde{q}, & \text{if } X_i \geq \tilde{q}. \end{cases}\] In other words, \(\tilde{X}_i = \min(X_i, \tilde{q})\). We now apply Lemma 13 to the distribution of \((\tilde{X}_1, \dots, \tilde{X}_k)\), which we denote by \(\tilde{\nu}\), and measure \(\tilde{\mu}\). To do so, we must verify condition 16 for \(\tilde{\nu}\) and \(\tilde{\mu}\).

Consider an arbitrary function \(\tilde{f} : [\tilde{q} + 1]^k \to \mathbb{C}\) that depends on at most \(t\) variables. Define \(f : [q]^k \to \mathbb{C}\) as follows: \[f(a_1, \dots, a_k) = \tilde{f}(\min(a_1, \tilde{q}), \dots, \min(a_k, \tilde{q})).\] Then, \(\tilde{f}(\tilde{X}_1, \dots, \tilde{X}_k) = f(X_1, \dots, X_k)\) and \(\mathbb{E}[\tilde{f}(\tilde{X}_1, \dots, \tilde{X}_k)] = \mathbb{E}[f(X_1, \dots, X_k)]\). Similarly, let \((M_1, \dots, M_k)\) and \((\tilde{M}_1, \dots, \tilde{M}_k)\) be random variables with joint distributions given by \(\mu^{\otimes k}\) and \(\tilde{\mu}^{\otimes k}\), respectively. Then, \(\mathbb{E}[\tilde{f}(\tilde{M}_1, \dots, \tilde{M}_k)] = \mathbb{E}[f(M_1, \dots, M_k)]\). Inequality 16 is equivalent to \[\left| \mathbb{E}[f(X_1, \dots, X_k)] - \mathbb{E}[f(M_1, \dots, M_k)] \right| \leq \epsilon \|f\|_{\infty}.\] We have \[\Big| \mathbb{E}[\tilde{f}(\tilde{X}_1, \dots, \tilde{X}_k)] - \mathbb{E}[\tilde{f}(\tilde{M}_1, \dots, \tilde{M}_k)] \Big| = \Big| \mathbb{E}[f(X_1, \dots, X_k)] - \mathbb{E}[f(M_1, \dots, M_k)] \Big| \leq \epsilon \|f\|_{\infty}.\]

Therefore, we can apply Lemma 13 to the distributions \(\tilde{\nu}\) and \(\tilde{\mu}\). By this lemma, there exist \(t\)-wise \(\tilde{\mu}\)-independent random variables \(\tilde{Y}_1, \dots, \tilde{Y}_k\) such that the total variation distance between the distributions of \(\tilde{X}_1, \dots, \tilde{X}_k\) and \(\tilde{Y}_1, \dots, \tilde{Y}_k\) is at most \[\label{eq:dTV-tX-tY} \binom{k}{t} \cdot \tilde{\gamma}^{-k}\cdot (\tilde{q} + 1)^t \epsilon = \binom{k}{t} \cdot \gamma^{-k} \; \frac{q^k}{(\tilde{q} + 1)^k} \cdot (\tilde{q} + 1)^t \epsilon \leq \left(\frac{2q}{\gamma} \right)^k \epsilon.\tag{17}\] Here, we used the fact that the random variables are defined on \([\tilde{q} + 1]^k\), and that \(\tilde{\mu}(z) \geq \tilde{\gamma}/(\tilde{q} + 1)\).

Finally, we define the desired random variables \(Y_1, \dots, Y_k\) as follows: if \(\tilde{Y}_i < \tilde{q}\), we let \(Y_i = \tilde{Y}_i\). If \(\tilde{Y}_i = \tilde{q}\), then we let \(Y_i = a_i\) with probability \[\frac{\mu(a_i)}{\mu(\{\tilde{q}, \dots, q - 1\})} \quad \text{for } a_i \geq \tilde{q},\] independently for all \(i\).

We verify that \(Y_1, \dots, Y_k\) are \(t\)-wise \(\mu\)-independent random variables. Each \(Y_i\) depends only on \(\tilde{Y}_i\) and a random coin toss (used to select the value of \(Y_i\) if \(\tilde{Y}_i = \tilde{q}\)), which is independent of all other variables. Thus, if \(\tilde{Y}_{i_1}, \dots, \tilde{Y}_{i_t}\) are independent, then so are \(Y_{i_1}, \dots, Y_{i_t}\). We get that \(Y_1,\dots,Y_k\) are \(t\)-wise independent. For every \(a_i<\tilde{q}\), \[\Pr(Y_i = a_i) = \Pr(\tilde{Y}_i = a_i) = \mu(a_i).\] For \(a_i \geq \tilde{q}\), we have \[\Pr(Y_i = a_i) = \Pr(\tilde{Y}_i = \tilde{q}) \cdot \frac{\mu(a_i)}{\mu(\{\tilde{q}, \dots, q - 1\})} = \mu(a_i).\] Therefore, the marginal distribution of each \(Y_i\) is \(\mu\).

It only remains to bound the total variation distance between the distributions of \((X_1, \dots, X_k)\) and \((Y_1, \dots, Y_k)\). The total variation distance between \((\tilde{X}_1, \dots, \tilde{X}_k)\) and \((\tilde{Y}_1, \dots, \tilde{Y}_k)\) is at most \(\big( \frac{2q}{\gamma} \big)^k \epsilon \quad \text{(see~\eqref{eq:dTV-tX-tY})}\). The total variation distance between \((X_1, \dots, X_k)\) and \((\tilde{X}_1, \dots, \tilde{X}_k)\) is \[\Pr(\exists i \text{ such that } X_i \neq \tilde{X}_i) = \Pr(\exists i \text{ such that } X_i > \tilde{q}) \leq \sum_{i=1}^{k-1} \Pr(X_i > \tilde{q}).\] Each \(\Pr(X_i > \tilde{q})\) is upper bounded by \(\mu(\{\tilde{q}+1, \dots, q - 1\}) + \epsilon\), because \[\Pr(X_i > \tilde{q}) = \mathbb{E}[\mathbf{1}\{X_i > \tilde{q}\}] \leq \mu(\{\tilde{q}+1, \dots, q - 1\}) + \epsilon,\] as the indicator function \(\mathbf{1}\{X_i > \tilde{q}\}\) depends only on the single variable \(X_i\). Hence, \[\Pr(\exists i \text{ such that } X_i \neq \tilde{X}_i) \leq k \left( \mu(\{\tilde{q}+1, \dots, q - 1\}) + \epsilon \right) \leq kq\gamma + k\epsilon.\] Similarly, the total variation distance between \((Y_1, \dots, Y_k)\) and \((\tilde{Y}_1, \dots, \tilde{Y}_k)\) is \[\Pr(\exists i \text{ such that } Y_i \neq \tilde{Y}_i) = \Pr(\exists i \text{ such that } {Y}_i > \tilde{q}) \leq \sum_{i=1}^k \Pr({Y}_i > \tilde{q}) = k \mu(\{\tilde{q}+1, \dots, q - 1\}) \leq kq\gamma.\]

Therefore, by the triangle inequality, the total variation distance between the distributions of \((X_1, \dots, X_k)\) and \((Y_1, \dots, Y_k)\) is at most \(\left( \frac{2q}{\gamma} \right)^k \epsilon + 2kq\gamma + k\epsilon\). Since \(\gamma = \epsilon^{1/(k+1)}\), we obtain the bound \[(2q)^k \epsilon^{1/(k+1)} + 2kq \epsilon^{1/(k+1)} + k\epsilon = O\left((2q)^k \epsilon^{1/(k+1)}\right).\] ◻

Proof. We will, equivalently, lower bound the probability of the event that \(f_{\mathrm{\textsf{btw}}}(a,b,c)=0\). We have that: \[\begin{align} \Pr\big(f_{\mathrm{\textsf{btw}}}(a,b,c)=0\big)\geq \Pr\big(b\leq \frac{1}{2} \text{ and } a,c>b\big)+\Pr\big(b> \frac{1}{2} \text{ and } a,c< b\big) \end{align}\] We bound the probability \(\Pr\big(b\leq \frac{1}{2} \text{ and } a,c>b\big)\), we have that: \[\begin{align} \Pr\big(b\leq \frac{1}{2} \text{ and } a,c\geq b\big)&=\int_{0}^{1/2}\textrm{Pr}\left[\, a,c\geq b \, \middle| \, b=x \,\right]dx\\ &=\int_{0}^{1/2}(1-\textrm{Pr}\left[\, a< x \text{ or }c<x \, \middle| \, b=x \,\right])dx\\ &\geq \int_{0}^{1/2}(1-\textrm{Pr}\left[\, a<x \, \middle| \, b=x \,\right]-\textrm{Pr}\left[\, c<x \, \middle| \, b=x \,\right])dx\\ &=\int_{0}^{1/2}(1-2x) dx\\ &=\frac{1}{4}. \end{align}\] By symmetry, we also get that \(\Pr\big(b>\frac{1}{2} \text{ and } a,c<b\big)\geq \frac{1}{4}\), which gives the result. ◻

Proof. Observe that \(\Pr\big(f_{\mathrm{\textsf{btw}}}(a,c,b)=1\big)=0\) and furthermore, by symmetry, \(\Pr\big(f_{\mathrm{\textsf{btw}}}(a,b,c)=1\big)=\Pr\big(f_{\mathrm{\textsf{btw}}}(b,a,c)=1\big)\), meaning that: \[\begin{align} \Pr\big(f_{\mathrm{\textsf{btw}}}(a,b,c)=1\big)=\frac{1}{2} \end{align}\] ◻

Proof. We will prove a stronger statement, that \(f_{\mathrm{\textsf{cyc}}}\) is satisfied with probability exactly \(\frac{1}{2}\), if \((a,b,c)\) is sampled from a pairwise uniform distribution over \([0,1]^3\). The proof follows from the observation that we can write the predicate \(f_{\mathrm{\textsf{cyc}}}\) is as the sum of a constant term and functions that only depend on \(2\) out of the three variables. In particular, we have that: \[\begin{align} f_{\mathrm{\textsf{cyc}}}(a,b,c)=\frac{1}{2}+\frac{1}{2}\left(\mathop{\mathrm{sign}}(b-a)+\mathop{\mathrm{sign}}(c-b)+\mathop{\mathrm{sign}}(a-c)\right) \end{align}\] We have that: \[\begin{align} \Pr\big(f_{\mathrm{\textsf{cyc}}}(a,b,c)=1\big)&=\mathbb{E}[f_{\mathrm{\textsf{cyc}}}(a,b,c)]\\ &=\frac{1}{2}+\frac{1}{2}\mathbb{E}[\mathop{\mathrm{sign}}(b-a)+\mathop{\mathrm{sign}}(c-b)+\mathop{\mathrm{sign}}(a-c)]\\ &=\frac{1}{2} \end{align}\] ◻

Proof. Fix a positive \(c\). If \(c\leq 1\), then all components in \(\mathbb{G}(n,c/n)\) have size \(o(n)\) w.h.p., and Part I follows. If \(c\geq\lambda_r^*\), then Part I is trivial because \(\psi_r(c)=1\). Thus, we assume that \(c\in(1,\lambda_r^*)\).

Let \(\rho=\rho(c)\) be the asymptotic fraction of vertices in the giant component of \(\mathbb{G}(n,c/n)\). By Theorem 7, the largest connected component has size \((\rho+o(1))n\) w.h.p. Moreover, \(\rho\) satisfies \(1-\rho=e^{-c\rho}\), or equivalently, \(c=-\ln(1-\rho)/\rho\). Therefore, by the definition of \(\lambda_r^*\), \[\lambda_r^* \leq \frac{-\ln(1-\rho)}{\rho(1-(1-\rho)^r)} = \frac{c}{1-(1-\rho)^r}.\] Hence \(1-(1-\rho)^r\leq c/\lambda_r^*\), and since \(c<\lambda_r^*\), we get \[\rho \leq 1-\left(1-\frac{c}{\lambda_r^*}\right)^{1/r} = \psi_r(c).\] This proves Part I.

We now prove Part II. Let \(s_r^*\in(0,1)\) be a point where the function \(h_r(s)=-\ln(1-s)/(s(1-(1-s)^r))\) attains its minimum, and let \(c_r^*=-\ln(1-s_r^*)/s_r^*\). Since \(h_r(s_r^*)=\lambda_r^*\), we have \(c_r^*=\lambda_r^*(1-(1-s_r^*)^r)\). Therefore, \(\psi_r(c_r^*)=s_r^*\). Also, the equation defining \(c_r^*\) is equivalent to \(1-s_r^*=e^{-c_r^*s_r^*}\). Thus, \(s_r^*\) is the giant-component fraction in \(\mathbb{G}(n,c_r^*/n)\). By Theorem 7, the largest connected component in \(\mathbb{G}(n,c_r^*/n)\) has size \((s_r^*+o(1))n\) w.h.p. Since \(s_r^*=\psi_r(c_r^*)\), Part II follows. ◻

Proof. Let \(L(x)=-\ln(1-g(x))\). Then \(L(x)>0\) on \(\left[\frac{1}{3},\frac{1}{2}\right]\), and \[f(x)=\frac{H(x)}{L(x)}.\] We prove that \(f'(x)<0\) for \(x\in\left(\frac{1}{3},\frac{1}{2}\right)\). Write, \[f'(x) = \frac{H'(x)L(x)-H(x)L'(x)}{L(x)^2}.\] We show that the numerator is negative, or equivalently, that the following expression is positive: \[H(x)L'(x)-L(x)H'(x) = (H(x)-L(x))L'(x)+L(x)(L'(x)-H'(x)).\] To do so, we prove that \(L'(x) \geq 0\); \(H(x)-L(x)>0\); and \(L'(x)-H'(x)>0\).

Observe that both \(H\) and \(L\) are increasing, since \(H\) is the binary entropy (increasing on \([0,1/2]\)) and \(L\) is increasing because \(g(x)=(2x(1-x))^2\) is increasing on \([1/3,1/2]\). Thus, \(L'(x)\geq 0\) (as \(L(x)\) is differentiable). Also, since \(H(1/3) > L(1/2)\), we have \[H(x) \geq H(1/3) > L(1/2) \geq L(x) \qquad \text{for }x\in\left[\frac{1}{3},\frac{1}{2}\right].\] It remains to prove that \(L'(x)>H'(x)\) for \(x\in\left(\frac{1}{3},\frac{1}{2}\right)\). Let \(y=1-2x\). Then \(0<y<1/3\), and \[\begin{align} H'(x) &= \ln\frac{1-x}{x} = \ln\frac{1+y}{1-y} = 2\operatorname{arctanh} y,\\ L'(x)&=\frac{g'(x)}{1-g(x)} = \frac{8x(1-x)(1-2x)}{1-4x^2(1-x)^2} = \frac{8y(1-y^2)}{3+2y^2-y^4}. \end{align}\] Therefore, in order to prove that \(L'(x)>H'(x)\), it suffices to show that \[\operatorname{arctanh} y < \frac{4y(1-y^2)}{3+2y^2-y^4}.\] We bound the left-hand side as follows: \[\operatorname{arctanh}y = \sum_{n=0}^{\infty}\frac{y^{2n+1}}{2n+1} \le y+\frac{1}{3}\sum_{n=1}^{\infty}y^{2n+1} = \frac{y(3-2y^2)}{3(1-y^2)}.\] We now verify that this last expression is smaller than \(\frac{4y(1-y^2)}{3+2y^2-y^4}\). Since all denominators are positive and \(y>0\), this is equivalent to \((3-2y^2)(3+2y^2-y^4)<12(1-y^2)^2\). Expanding, the difference between the right-hand side and the left-hand side is \[12(1-y^2)^2-(3-2y^2)(3+2y^2-y^4) = 3-24y^2+19y^4-2y^6.\] This is positive for \(0<y<1/3\), because \(3-24y^2>\frac{1}{3}\) and \(19y^4-2y^6>0\). Hence \(L'(x)>H'(x)\).

This completes the proof that \(f'(x)<0\) for \(x\in\left(\tfrac13,\tfrac12\right)\). Hence, \(f\) is decreasing on \(\left[\tfrac13,\tfrac12\right]\). ◻

Proof. Pick an integer \(q > 8k^2/\epsilon\). Fix a coarse solution \(\xi \in \Xi_{\frac{16}{q}, q}\). We shall use this solution to define a biased random assignment algorithm. First, the algorithm randomly and independently assigns each variable \(x \in V\) to a leaf \(l\) with probability \(n_l/n\), where \(n_l = |\{x : \xi(x) = l\}|\) is the number of variables assigned to leaf \(l\) by the coarse solution \(\xi\). Then, it recursively partitions variables in each leaf splitting them with a 50%-50% probability at every step. We call this biased randomized assignment algorithm the \(\xi\)-biased algorithm and denote its approximation factor by \(\alpha_\xi(f_{\mathrm{\textsf{phy}}})\). In other words, \(\alpha_\xi(f_{\mathrm{\textsf{phy}}})\) is the expected value of the solution created by the \(\xi\)-biased algorithm.

Consider arbitrary \(k\) variables \(y^1,\dots,y^k\). The \(\xi\)-biased algorithm first assigns \(y^1,\dots,y^k\) to random leaves \(\zeta(y^1),\dots,\zeta(y^k)\) and then after recursively splitting variables in the leaves assigns \(y^1,\dots,y^k\) to \(\eta(y^1),\dots, \eta(y^k)\). If leaves \(\zeta(y^1),\dots,\zeta(y^k)\) are all distinct, then \[f_{\mathrm{\textsf{phy}}}(\zeta(y^1),\dots,\zeta(y^k)) = f_{\mathrm{\textsf{phy}}}(\eta(y^1),\dots,\eta(y^k)).\] Moreover, if leaves \(\zeta(y^1),\dots,\zeta(y^k)\) have distinct colors, then \[f_{\mathrm{\textsf{phy}}}^+(\zeta(y^1),\dots,\zeta(y^k)) = f_{\mathrm{\textsf{phy}}}(\zeta(y^1),\dots,\zeta(y^k)) = f_{\mathrm{\textsf{phy}}}(\eta(y^1),\dots,\eta(y^k)).\]

The probability that two or more leaves among \(\zeta(y^1),\dots,\zeta(y^k)\) have the same color is at most \(\frac{16}{q}\cdot \binom{k}{2} < \epsilon\), because the probability that variable \(y^j\) is assigned to a leaf of any given color is at most \(16/q\) (by the definition of class \(\Xi_{\frac{16}{q},q}\)). Therefore, we have \[\mathbb{E}[f_{\mathrm{\textsf{phy}}}^+(\zeta(y^1),\dots,\zeta(y^k))] \leq \mathbb{E}[f_{\mathrm{\textsf{phy}}}(\eta(y^1),\dots,\eta(y^k))] + \epsilon = \alpha_{\xi}(f_{\mathrm{\textsf{phy}}}) +\epsilon\leq \alpha^*(f_{\mathrm{\textsf{phy}}}) + \epsilon.\]

Now consider one of the constraints \((X_i^1, \dots, X_i^k)\) in the random instance \(\mathcal{I}_{f_{\mathrm{\textsf{phy}}}}(n,m)\). Variables \(X_i^1, \dots, X_i^k\) are chosen randomly in \(V\) and then mapped to the leaves of \(T_\xi\) by the coarse solution \(\xi\). Since \(n_u\) variables from \(V\) are mapped to leaf \(u\), we have \(\Pr(\xi(X_i^j) = u) = n_u/n\). Thus, each \(\xi(X_i^j)\) has the same marginal distribution as \(\zeta(y^j)\). Note that \(\xi(X_i^1),\dots,\xi(X_i^k)\) are not independent since \(X_i^1,\dots,X_i^k\) are chosen in \(V\) without replacement. So, the distributions of the tuples \((\zeta(y^1),\dots,\zeta(y^k))\) and \((\xi(X_i^1),\dots,\xi(X_i^k))\) are not identical but they are very close if \(n\) is sufficiently large. Indeed, let \(\tilde{X}^1,\dots, \tilde{X}^k\) be \(k\) random variables sampled in \(V\) with replacement. Then, \((\zeta(y^1),\dots,\zeta(y^k))\) and \((\xi(\tilde{X}^1),\dots,\xi(\tilde{X}^k))\) have the same distribution, and the total variation distance between distributions of \((X_i^1,\dots,X_i^k)\) and \((\tilde{X}^1,\dots, \tilde{X}^k)\) is at most \(\binom{k}{2}/n\), which is an upper bound on the probability that \(\tilde{X}^a = \tilde{X}^b\) for some \(a\) and \(b\). This probability is less than \(\epsilon\) for sufficiently large \(n\). Hence, \[\mathbb{E}[f_{\mathrm{\textsf{phy}}}^+(\xi(X_i^1),\dots,\xi(X_i^k))] \leq \mathbb{E}[f_{\mathrm{\textsf{phy}}}^+(\zeta(y^1),\dots,\zeta(y^k))] + \epsilon \leq \alpha^*(f_{\mathrm{\textsf{phy}}}) + 2\epsilon.\] We showed that the expected “+”-value of every payoff function in \(\mathcal{I}_{f_{\mathrm{\textsf{phy}}}}(n,m)\) is at most \(\alpha^*(f_{\mathrm{\textsf{phy}}}) + 2\epsilon\). We now estimate the probability that the value \(\mathop{\mathrm{val}}^+(\xi,\mathcal{I}_{f_{\mathrm{\textsf{phy}}}}(n,m))\) of the instance is larger than \(\alpha^*(f_{\mathrm{\textsf{phy}}}) + 3\epsilon\). By Hoeffding’s inequality, we have \[\Pr\big[\mathop{\mathrm{val}}^+(\xi,\mathcal{I}_{f_{\mathrm{\textsf{phy}}}}(n,m)) \geq \alpha^*(f) + 3\epsilon\big] \leq e^{-2\epsilon^2 m}.\] The number of all coarse solutions in \(\Xi_{\frac{16}{q},q}\) is upper bounded by \(q^{3q}q^n\) (there are at most \(q^q\) trees with \(q\) leaves; for each tree there are at most \(q!<q^q\) orderings of the leaves and each tree can be colored in at most \(q^q\) different ways; there are at most \(q^n\) ways to assign variables in \(V\) to the leaves of the tree). Using the union bound over all coarse solutions \(\xi\) in \(\Xi_{\frac{16}{q},q}\), we get \[\Pr\left[\exists \xi \in \Xi_{\frac{16}{q}, q} : \mathop{\mathrm{val}}^+(\xi,\mathcal{I}_{f_{\mathrm{\textsf{phy}}}}(n,m)) \geq \alpha^*(f_{\mathrm{\textsf{phy}}}) + 3\epsilon\right] \leq q^{3q} \cdot q^n \cdot e^{-2\epsilon^2 m} = q^{3q} \cdot e^{-(2\epsilon^2 C-\ln q)n} .\] This probability tends to \(0\) as \(n\) tends to infinity if \(C > \frac{\ln q}{2\epsilon^2}\). This finishes the proof. ◻