Let $\phi$ be a Boolean function on $k$ inputs of degree hardness $\Hdeg(\phi) \leq 2 < k$. Then $\VOpt(\phi)$ can be solved in time $\Order(m^{k-\delta})$, for some $\delta > 0$.

§.§ The Equivalence to

In the course of the previous subsections, we proved both upper and lower bounds by connecting the optimization problems $\VOpt(\phi)$ of degree hardness $\Hdeg(\phi) = h$ to clique detection in $h$-uniform hypergraphs. <ref> summarizes both directions:

By the equivalence of general problems $\Opt(\psi)$ and vector optimization problems $\VOpt(\phi)$ (<ref>), we only need to show the statement for vector problems $\VOpt(\phi)$. The second item is proven in <ref>. The first item is proven in <ref>, but only for $h \geq 3$. Nevertheless, exactly the same proof works also for $h = 2$.

<ref> strengthens the evidence for the h hypothesis (at least for the stronger version postulating no $\Order(n^{h+1-\delta})$ algorithm for the hh+1 problem), but we consider it an interesting result also for two additional reasons.

First, in the specific case $\Hdeg(\psi) = 2$, <ref> yields an explanation on why we can, but also need to use fast matrix multiplication to efficiently solve $\Opt(\psi)$. Indeed, any algorithm solving $\Opt(\psi)$ in time $\Order(m^{k-\delta})$, translates directly to an algorithm for finding cliques in (ordinary) graphs in time $\Order(n^{k-\delta'})$ – an improvement, which is labeled highly unlikely without the use of fast matrix multiplication [4].

Second, it is interesting to compare <ref> to a similar, yet different equivalence result [31]: The h hypothesis holds if and only if for all $k \geq h$, and all $\MinSP_k$ graph formulas $\psi$ of and-hardness $\Hand(\psi) = h$, $\Zero(\psi)$ requires time $\Order(m^{k-\delta})$ for all $\delta > 0$. That equivalence is about classes (in that it relates the class of h problems with the class of all problems $\Zero(\psi)$ of and-hardness $h$), whereas <ref> is more problem-centered (in the sense that every specific graph formula $\psi$ is related with certain h problems).

§ APPROXIMATION ALGORITHMS FOR MAXIMIZATION

In this section, we give our algorithmic results for approximating the maximization variant of our problems. As illustrated in <ref>, there are three regimes of interest.
We first present elementary constant-factor approximation algorithms (<ref>) and polynomial-factor approximation algorithms (<ref>). In <ref> we then obtain approximation schemes by a reduction to the polynomial method.

§.§ Constant-Factor Approximation

In this section, we provide a proof for the algorithmic part of <ref>. Phrased in terms of vectors problems (which is equivalent by <ref>), we prove that:

Let $\phi$ be a Boolean function on $k$ inputs. If $\Hand(\phi) < k$ (or equivalently, $\phi$ does not have exactly one satisfying assignment), then there exists a constant-factor approximation for $\VMax(\phi)$ in time $\Order(m^{k-1})$.

We start with a definition. Let $\phi : \{0, 1\}^k \to \{0, 1\}$ be a Boolean function with the following property: Whenever $\alpha$ is a satisfying assignment of $\phi$, then the component-wise negation of $\alpha$ is also satisfying. We call $\phi$ an opposite function. We proceed in three steps:

* Exploiting the formula's structure, we design a constant approximation algorithm for all problems $\VMax(\phi)$ where $\phi$ is an opposite function (<ref>).

* As a consequence, we turn this algorithm into a constant approximation for all problems $\VMax(\phi)$ where $\phi$ has exactly two (arbitrary) satisfying assignments (<ref>).

* Finally, let $\phi$ have at least two satisfying assignments. We can “cover” all satisfying assignments by pairs and apply the previous algorithm (<ref>).

Let $\phi$ be a $k$-variable opposite function. Then there exists a $(k + 1)$-approximation for $\VMax(\phi)$ in time $\Order(m^{k-1})$.

The proof of <ref> relies on the following simple proposition:

Let $\phi$ be a $k$-variable opposite function and let $a_1, \ldots, a_k, b_1, \ldots, b_k \in \{0, 1\}$. Then:

\begin{equation*}
\phi(a_1, \ldots, a_k) \leq \phi(b_1, \ldots, b_k) + \sum_{1 \leq i \leq k} \phi(a_1, \ldots, a_{i-1}, b_i, a_{i+1}, \ldots, a_k).
\end{equation*}

If the $a_i$'s do not satisfy $\phi$, then the claimed inequality trivially holds. Thus, assume that $\phi(a_1, \ldots, a_k) = 1$. We distinguish two cases: If there exists some index $i$ with $b_i = a_i$, we have that $\phi(a_1, \ldots, a_{i-1}, b_i, a_{i+1}, \ldots, a_k) = 1$ as well. Hence, one of the terms in the sum on the right-hand side equals one. Otherwise, we have $b_i \neq a_i$ for all $i$. Recall that $\phi$ is opposite and $\phi(a_1, \ldots, a_k) = 1$, thus $\phi(b_1, \ldots, b_k) = 1$ and we also have a contribution of at least one on the right-hand side.

The previous proposition immediately suggests the following algorithm for $\VMax(\phi)$. Let $X_1, \ldots, X_k$ be the given sets of vectors.

* Pick $k$ arbitrary vectors $\hat x_1 \in X_1, \ldots, \hat x_k \in X_k$.

* Compute

\begin{equation*}
v_0 := \counting_{y \in Y} \phi(\hat x_1[y], \ldots, \hat x_k[y]).
\end{equation*}

* Compute

\begin{equation*}
v_i := \max_{x_1, \ldots, x_{i-1}, x_{i+1}, \ldots, x_k} \counting_{y \in Y} \phi(x_1[y], \ldots, x_{i-1}[y], \hat x_i[y], x_{i+1}[y], \ldots, x_k[y])
\end{equation*}
for all $i \in [k]$, using the $\MaxSP_{k-1}$ baseline algorithm.

* Return $v := \max_i v_i$.

We first analyze the approximation ratio. Obviously, the algorithm never returns an overestimation: $v \leq \OPT$. Let $(x_1, \ldots, x_k)$ be vectors corresponding to an optimal solution and fix an arbitrary coordinate $y$ for which $\phi(x_1[y], \ldots, x_k[y])$ holds. From <ref> it follows that $y$ contributes $1$ to at least one of the values $v_0, v_1, \ldots, v_k$. Hence, by the pigeonhole principle, there exists an index $i$ such that $v_i \geq \OPT/(k + 1)$. In particular, we have $v \geq \OPT/(k + 1)$ and thus the algorithm indeed computes a $(k + 1)$-approximation.

Next, focus on the running time. Steps 1, 2 and 4 are executed in linear time. The third step invokes the $\MaxSP{k-1}$ baseline algorithm a constant number of times which takes time $\Order(m^{k-1})$ in total.

Let $\phi$ be a Boolean function on $k$ inputs with exactly two satisfying assignments. Then there exists a $(k + 1)$-approximation for $\VMax(\phi)$ in time $\Order(m^{k-1})$.

Let $\alpha, \beta \in \{0, 1\}^k$ be the two satisfying assignments of $\phi$. Without loss of generality, we may assume that $\alpha_i \neq \beta_i$ for all $1 \leq i \leq r$ and $\alpha_i = \beta_i$ for all $r < i \leq k$, by reordering the indices $i$ if necessary. We distinguish the following cases for $r$:

* $r < 1$: This case is contradictory, since $\alpha$ and $\beta$ are distinct.

* $r = 1$: Here $\alpha_1 \neq \beta_1$ is the only position in which $\alpha$ and $\beta$ differ, so $\phi$ does not depend on the first input. Therefore, we can use the $\MaxSP_{k-1}$ baseline algorithm to solve the problem in time $\Order(m^{k-1})$.

* $r > 1$: We brute-force over all vectors $x_i$, $r < i \leq k$. What remains is a vector maximization problem $\VMax(\phi')$ on $r$ vectors, where $\phi'$ is an opposite function. Therefore we can apply <ref> to solve any instance in time $\Order(m^{r-1})$. We repeat this step for all $n^{k-r}$ choices of $x_{r+1}, \ldots, x_k$ and obtain a total running time of $\Order(n^{k-r} m^{r-1}) = \Order(m^{k-1})$.

If $\phi$ is the constant $\false$ function, then the problem is trivial. So let $\alpha^1, \ldots, \alpha^\ell$ denote the satisfying assignments of $\phi$, where $\ell \geq 2$.

* For all indices $1 \leq i \leq k$, let $\phi^i : \{0, 1\}^k \to \{0, 1\}$ be the indicator function of $\alpha^1$ and $\alpha^i$. That is, $\phi^i(z) = 1$ if and only if $z = \alpha^1$ or $z = \alpha^i$.

* Compute a $(k + 1)$-approximation $v^i$ for $\VMax(\phi^i)$ using <ref>.

* Return $\max_i v^i$.

The number of iterations in step 2 is bounded by $\ell = \Order(1)$, so the running time is bounded by $\Order(m^{k-1})$.

To analyze the approximation performance, let $(x_1, \ldots, x_k)$ be an optimal solution of value $\OPT$, and let $\alpha_i$ be the satisfying assignment which occurs most frequently in $(x_1, \ldots, x_k)$. Then, by the pigeonhole principle, it follows that the optimal value of $\VMax(\phi^i)$ is at least $\OPT/\ell$. Since $v^i$ is a $(k + 1)$-approximation to that maximization problem, it follows that $v^i \geq 1/(k + 1) \mult \OPT/\ell = \Omega(\OPT)$, so our algorithm outputs a constant-factor approximation.

§.§ Polynomial-Factor Approximation

Next, we show that even the hardest maximization problems admit polynomial-factor approximations thereby proving the upper bound in <ref>. Recall that hereby, we mean polynomial factors in $m$. Our algorithm heavily exploits the sparse input representation.

Let $\phi$ be an arbitrary Boolean function on $k$ inputs. Then, for any $\varepsilon > 0$, there exists some $\delta > 0$ such that an $m^\varepsilon$-approximation of $\VMax(\phi)$ can be computed in time $\Order(m^{k-\delta})$.

As a first step towards proving <ref>, we prove the following simple lemma:

Let $\phi$ be a Boolean function on $k$ inputs with exactly one satisfying assignment. Then, given a $\VMax(\phi)$ instance, we can decide distinguish whether $\OPT = 0$ or $\OPT > 0$ in time $\Order(m)$.

Notice that <ref> does not hold for minimization, which is the reason why we cannot give polynomial-factor approximations for $\VMin(\phi)$.

Let $\alpha \in \{0, 1\}^k$ be the satisfying assignment of $\phi$. Observe that $\OPT = 0$ if and only if, for all $i \in [k]$, all vectors $x_i \in X_i$ and all coordinates $y \in Y$, $x_i[y] \neq \alpha_i$. Therefore, it suffices to check individually for each set $X_i$, whether it contains some vector with an entry equal to $\alpha_i$. Clearly this takes time at most $\Order(m)$.

We have already shown how to compute constant approximations for all functions $\phi$ in time $\Order(m^{k-1})$, except for those with exactly one falsifying assignment (<ref>). Thus, assume that $\phi$ has exactly one satisfying assignment $\alpha \in \{0, 1\}^k$. We distinguish two cases:

Case 1: $\alpha_i = 1$ for some $i$. Without loss of generality, we assume that $i = 1$. We split $X_1$ into a sparse part $X_1^{\text{sparse}} = \{ x_1 \in X_1 : \text{$x_1$ has Hamming weight $\leq m^\varepsilon$} \}$ and a dense part $X_1^{\text{dense}} = X_1 \setminus X_1^{\text{sparse}}$ and separately solve the instances $(X_1^{\text{sparse}}, X_2, \ldots, X_k, Y)$ and $(X_1^{\text{dense}}, X_2, \ldots, X_k, Y)$. In the sparse instance it holds that $\OPT \leq m^\varepsilon$. Thus, it suffices to check whether $\OPT > 0$ to compute an $m^\varepsilon$-approximation. By <ref>, this can be checked in time linear time.

We are left with the dense instance, which can be solved exactly efficiently: Since every vector in $X_i^{\text{dense}}$ is of Hamming weight at least $m^\varepsilon$, there can be at most $m / m^\varepsilon = m^{1 - \varepsilon}$ vectors in $X_i^{\text{dense}}$. Therefore, we can brute-force over all $x_1 \in X_i^{\text{dense}}$ and solve the remaining $\MaxSP_{k-1}$ problem in time $\Order(m^{k-1})$ using the baseline algorithm. The total running time is $\Order(m^{1-\varepsilon} m^{k-1}) = \Order(m^{k-\varepsilon})$.

Case 2: $\alpha_i = 0$ for all $i$. As before, let $d = |Y|$. If $d \leq m^\varepsilon$, then it again suffices to decide whether $\OPT > 0$ (which takes linear time by <ref>) to compute an $m^\varepsilon$-approximation. So we may assume that $d > m^\varepsilon$. We in fact show how to compute a constant-factor approximation. We call a vector $x_i$ light if its Hamming weight is at most $d / (k + 1)$, and heavy otherwise. If there exist light vectors $x_1 \in X_1, \ldots, x_k \in X_k$, then we have detected a solution of value $\geq d - k \mult d / (k + 1) = d / (k + 1) \geq \OPT / (k + 1)$.

Otherwise, some set $X_i$ contains only heavy vectors and therefore contains at most $|X_i| \leq (k + 1)m / d \leq \Order(m^{1-\varepsilon})$ vectors. After enumerating all vectors $x_i \in X_i$, it suffices to solve the remaining $\MaxSP_{k-1}$ problem using the baseline algorithm in time $\Order(m^{k-1})$. Again, the total running time is $\Order(m^{1-\varepsilon} m^{k-1}) = \Order(m^{k-\varepsilon})$.

§.§ Approximation Schemes via Polynomial Method

In this section, we give the approximation scheme claimed in <ref>. Although a similar approach also works for the minimization variants, we will omit their treatment here and instead prove the relevant claims about minimization in <ref>. By the equivalence of vector optimization problems, it suffices to prove the following lemma:

Let $\phi$ be a Boolean function on $k$ inputs. If $\Hand(\phi) \leq 1$, then there exists a randomized approximation scheme for $\VMax(\phi)$.

The proof of <ref> ultimately traces back to an application of the polynomial method [11, 9]. However, as it turns out, it is not necessary to explicitly design algorithms in the style of the polynomial method for every problem considered here; instead, we show a black-box reduction to a problem which is already known to admit subquadratic approximation algorithms based on the polynomial method: . In the  problem, we are given two sets of $n$ bit-vectors $X_1, X_2 \subseteq \{ 0,1 \}^d$ and the task is to compute the maximum Hamming distance between any two vectors $x_1 \in X_1, x_2 \in X_2$. Let $\leftrightarrow$ denote the Boolean function computing “if and only if”. Then  is equivalent to $\VMax(z_1 \centernot\leftrightarrow z_2)$.

The following result about  occurs several times in the literature; in particular, it was proven by Alman, Chan and Williams [9]:

For any $\varepsilon > 0$, there exists some $\delta > 0$ such that we can compute an $(1 + \varepsilon)$-approximation for  in randomized time $\tilde\Order(nd + n^{2-\delta})$.

Their proof first uses a dimension reduction by locality-sensitive hashing in Hamming spaces. The improvement for the low-dimensional problem is then achieved by the polynomial method.

To state our reductions, recall the notion of a hybrid optimization problem as defined in <ref>. As a first step, we show how to obtain an approximation scheme for the hybrid problem of  and its complement:

Let $\Phi = \{ z_1 \centernot\leftrightarrow z_2, z_1 \leftrightarrow z_2 \}$. There exists a randomized approximation scheme for $\VMax(\Phi)$.

We introduce some notation: Let $Y_0 \subseteq Y$ denote the set of coordinates $y$ associated to $\phi_y(z_1, z_2) = (z_1 \leftrightarrow z_2)$ and let $Y_1 = Y \setminus Y_0$. Moreover, let $d_0 = |Y_0|$ and $d_1 = |Y_1|$. For a vector $x$ and a subset of dimensions $Y'$, let $\|x\|_{Y'} = |\{ y \in Y' : x[y] = 1 \}|$ denote the Hamming weight of $x$ restricted to $Y'$.

Our goal is to get rid of all coordinates in $Y_0$, as then the given hybrid instance effectively becomes an instance of . Following a naive approach, we would simply complement all entries $x_1[y]$, $y \in Y_0$. However, as $d_0$ might be as large as $n$, we cannot afford to complement directly. Instead, we will first modify the instance to guarantee that $n d_0 \leq \Order(m^{1.9})$. We have to further guarantee that $n d_1 \leq \Order(m^{1.9})$ to effectively apply the assumed  algorithm.

* To prove that we can assume $n d_1 \leq \Order(m^{1.9})$, suppose that otherwise $n d_1 \geq m^{1.9}$. It follows that $m \leq (nd_1)^{1/1.9} \leq n^{2/1.9} \leq n^{1.1}$. Let us call a vector $x_i$ heavy if $\|x_i\|_{Y_1} \geq n^{0.2}$, and light otherwise. Clearly, there can be at most $m / n^{0.2} \leq n^{1.1} / n^{0.2} = n^{0.9}$ heavy vectors and thus it is feasible to explicitly enumerate all heavy vectors $x_i$ and solve the remaining $\MaxSP_{k-1}$ problem exactly using the baseline algorithm in time $\Order(n^{0.9} m) = \Order(m^{1.9})$. In the remaining instance, there are only light vectors.

We now apply the following simple hashing scheme: Let $Y_1'$ be a set of size $|Y_1'| = d_1' := n^{0.9}$ and pick a random function $h : Y_1 \to Y_1'$. For every vector $x_i$, we construct a vector $x_i' \in \{0, 1\}^{Y_0 \union Y_1'}$ with $x_i'[y'] = \bigvee_{y \in h^{-1}(y')} x_i[y]$ for all $y' \in Y_1'$ and $x_i'[y] = x_i[y]$ for all $y \in Y_0$. Notice that the value of any pair $(x_1, x_2)$ can only decrease in the hashing step. Moreover, for any fixed pair $(x_1, x_2)$, with probability $1 - 2n^{2 \mult 0.2} / n^{0.9} = 1 - \Order(n^{-0.5})$, there occurs no collision in the hashing (i.e., no two $1$-entries are mapped to the same new coordinate) and thus the value of $(x_1', x_2')$ is the same as the value for $(x_1, x_2)$. In particular, with probability $1 - \Order(n^{-0.5})$, the optimal value does not change. In that way, we have effectively reduced $d_1 = |Y_1|$ to $n^{0.9}$, and thus $n d_1 \leq n^{1.9} \leq \Order(m^{1.9})$.

* Next, we prove that we can assume $n d_0 \leq \Order(m^{1.9})$. So suppose that $n d_0 \geq m^{1.9}$. Then $d_0 \geq m^{1.9} / n \geq \Omega(n^{0.9})$. Moreover, there exist vectors $x_1, x_2$ with $\|x_1\|_{Y_0} \leq d_0^{0.9}$ and $\|x_2\|_{Y_0} \leq d_0^{0.9}$ (as otherwise $m > n d_0^{0.9}$ and thus $m^{1.9} > n d_0$). But then the optimal value of this instance is very large: For most coordinates $y \in Y_0$, $x_1[y] = x_2[y] = 0$, which is satisfying for $(z_1 \leftrightarrow z_2)$. Thus, the optimal value is at least $\OPT \geq d_0 - d_0^{0.9} \geq (1 - \Omega(n^{-0.09})) d_0 \geq (1 - \varepsilon) d_0$ for any constant $\varepsilon > 0$ and sufficiently large $n$. Moreover, the contribution of all coordinates $y \in Y_1$ is at most $2n^{0.2}$ after eliminating all heavy vectors in the previous step. Therefore also $\OPT \leq d_0 + 2n^{0.2} \leq (1 + \varepsilon) d_0$ and we can safely return $x_1, x_2$ as an approximate optimal solution.

In combination, we can assume that $n d = n (d_0 + d_1) \leq \Order(m^{1.9})$. It is now feasible to complement all entries $x_1[y]$, $y \in Y_0$, in time $\Order(n d_0) = \Order(m^{1.9})$. What remains is a pure  instance. Observe that we increased the sparsity by a lot, however, the assumed  is insensitive to the sparsity $m$. Running that algorithm takes time $\Order(n d + n^{2-\delta}) = \Order(m^{1.9} + m^{2-\delta}) = \Order(m^{2-\delta'})$ for $\delta' := \min\{\delta, 0.1\} > 0$.

As $\Hand(\phi) \leq 1$, there exist two variables, say $z_1$ and $z_2$ without loss of generality, such that for any assignment to $z_3, \ldots, z_k$, the remaining two-variable formula does not have exactly one satisfying assignment. We start by brute-forcing over all $n^{k-2}$ tuples $(x_3, \ldots, x_k)$. For each tuple, we are left to solve a hybrid optimization problem $\VMax(\Phi')$, where $\Phi'$ potentially contains all $2$-variable functions $\phi'$ of hardness $\Hand(\phi') \leq 1$. We demonstrate how to eliminate any function $\phi' \not\in \Phi$. In the process, we pay attention to not increase the sparsity $m$ beyond a constant multiple. There are several cases for $\phi'$:

Case 0: $\phi'$ has 0 or 4 satisfying assignments. Then $\phi'$ trivially accepts or rejects every input and we can delete all coordinates $y$ associated with this type.

Case 1: $\phi'$ has 1 satisfying assignment. This case is contradictory since $\Hand(\phi') \leq 1$.

Case 2: $\phi'$ has 2 satisfying assignments.

Case 2a: $\phi'(z_1, z_2) = (z_1 \leftrightarrow z_2)$ or $\phi'(z_1, z_2) = (z_1 \centernot\leftrightarrow z_2)$.
Again, this case is trivial as $\phi'$ is already of the desired shape: $\phi' \in \Phi$.

Case 2b: $\phi'$ depends only on one input $z_i$. Without loss of generality, assume that $i = 1$. If $\phi'(z_1, z_2) = z_1$, we set every vector $x_2$ to zero (at all relevant coordinates $y$) and reinterpret $\phi'$ as $z_1 \centernot\leftrightarrow z_2$. Otherwise, if $\phi'(z_1, z_2) = \neg z_1$, we instead interpret $\phi'$ as $z_1 \leftrightarrow z_2$. This transformation is clearly correct and does not increase the sparsity, reducing Case 2b to Case 2a.

Case 3: $\phi'$ has 3 satisfying assignments. We can “cover” the three satisfying assignments by three pairs of assignments. For demonstration, consider the function $\phi'(z_1, z_2) = z_1 \lor z_2$. We run the previous reductions for the three functions $z_1 \centernot\leftrightarrow z_2$, $z_1$ and $z_2$ and concatenate the resulting vectors. For each of the three satisfying assignments $(1, 0)$, $(0, 1)$ and $(1, 1)$ of $\phi'$, exactly two functions among $z_1 \centernot\leftrightarrow z_2$, $z_1$ and $z_2$ are satisfied. As a result, we weighted the contribution of Case 3 by a factor of $2$. To compensate, we simply execute each of the previous cases twice and concatenate the output vectors. The optimal value of the resulting hybrid problem equals two times the former optimal value.

Running the approximation scheme for $\VMax(\Phi)$ takes time $\Order(m^{2-\delta})$, and we can recover the original optimal value by halving the output. Repeating these steps for all $n^{k-2}$ tuples $(x_3, \ldots, x_k)$ in the original instance takes time $\Order(n^{k-2} m^{2-\delta}) = \Order(m^{k-\delta})$.

§ APPROXIMATION ALGORITHMS FOR MINIMIZATION

In this section we give the algorithms for approximating $\VMin(\phi)$. Our goal is to prove the following <ref>. The upper bounds for both <ref> and <ref> follow immediately, by the equivalence of $\Min(\psi)$ and $\VMin(\phi)$.

Let $\phi$ be a Boolean function on $k$ inputs.

* If $\Hand(\phi) \leq 1$, then there exists a randomized approximation scheme for $\VMin(\phi)$.

* If $\Hand(\phi) \leq 2 < k$, then there exists a randomized constant-factor approximation algorithm for $\VMin(\phi)$ in time $\Order(m^{k-\delta})$, for some $\delta > 0$.
More generally: There exists a constant-factor approximation for $\VMin(\phi)$ in time $\Order(m^{k-\delta})$ for some $\delta > 0$ if and only if $\VZero(\phi)$ can be solved in time $\Order(m^{k-\delta'})$ for some $\delta' > 0$.

In contrast to the maximization case where we applied different techniques for each approximation regime, here all our results are a consequence of a general reduction from approximating $\VMin(\phi)$ to exactly solving $\VZero(\phi)$, where we use locality-sensitive hashing. Recall that $\VZero(\phi)$ is the problem of testing whether there exists a solution of value zero, or equivalently, testing whether $\OPT = 0$ for the minimization problem $\VMin(\phi)$. Our strategy is to first show that a sufficiently fast listing algorithm for $\VZero(\phi)$ implies the claimed approximation algorithms. Afterwards, we demonstrate how derive efficient listing algorithms for $\VZero(\phi)$, given the assumptions $\Hand(\phi) \leq 1 < k$ respectively $\Hand(\phi) \leq 2 < k$.

Formally, we call an algorithm a listing algorithm for $\VZero(\phi)$ if, given an integer $L$, it returns a list of $L$ distinct solutions $(x_1, \ldots, x_k)$ to $\VZero(\phi)$ (if there are less than $L$ distinct solutions, then it exhaustively lists all solutions). We usually parameterize the running time of listing algorithms with $T(m, L)$, where $m$ is the size of the input (as before).

We start with the following technical lemma, which generalizes the baseline algorithm to the case where only a subset of all tuples $(x_1, \dots, x_k)$ are considered candidate solutions.

Let $\phi$ be a Boolean function on $k$ inputs, and let $\delta > 0$. Given a $\VMin(\phi)$ instance, and a set of $\Order(n^{k-\delta})$ candidates $C \subseteq X_1 \times \dots \times X_k$, we can compute $\Val(x_1, \ldots, x_k)$ for all candidates $(x_1, \dots, x_k) \in C$ in time $\Order(m^{k-\delta/3})$.

The algorithm executes the following three steps:

* We call a vector $x_i$ heavy if its Hamming weight exceeds $m^{\delta/3}$, and light otherwise. As the total Hamming weight of all vectors is at most $\Order(m)$, there can be at most $\Order(m^{1-\delta/3})$ heavy vectors. Therefore, we can brute-force over all heavy vectors $x_k$ and solve the remaining $\MinSP_{k-1}$ problem in time $\Order(m^{k-1})$ using the baseline algorithm (which in fact computes all values $\Val(x_1, \ldots, x_k)$ in the same running time; see <cit.>). This step takes time $\Order(m^{k-\delta/3})$ and afterwards, we can assume that all vectors $x_k$ are light.

* Next, call a tuple $(x_1, \ldots, x_{k-1})$ a heavy prefix if the number of vectors $x_k$ such that $(x_1, \dots, x_k)$ is a candidate is at least $n^{1-2\delta/3}$. There can be at most $n^{k-1-\delta/3}$ heavy prefixes, as otherwise $|C| > n^{k-\delta}$. Enumerating all such prefixes and solving the remaining $\MinSP_1$ problem by the baseline algorithm takes time $\Order(n^{k-1-\delta/3} m) = \Order(m^{k-\delta/3})$.

* For any prefix $(x_1, \dots, x_{k-1})$ which is left, we can assume that there are at most $n^{1-2\delta/3}$ completions $x_k$ such that $(x_1, \dots, x_k)$ is a candidate. Moreover, recall that every such vector $x_k$ is light, and therefore of Hamming weight at most $\Order(m^{\delta/3})$. Hence, we brute-force over all remaining prefixes and solve a $\MinSP_1$ problem of size $\Order(n^{1-2\delta/3} m^{\delta/3})$. Again, we use the baseline algorithm, so this step takes time $\Order(n^{k-1} n^{1-2\delta/3} m^{\delta/3}) = \Order(m^{k-\delta/3})$ as well.

Let $\phi$ be a variable Boolean function on $k \geq 2$ inputs so that $L$ solutions to $\VZero(\phi)$ can be listed in time $T(m, L)$. Then, for any $c > 1$ and $0 < \gamma < k$, there is a randomized algorithm that with high probability computes a $c$-approximation of $\VMin(\phi)$ in time

\begin{equation*}
\tilde\Order\!\left(m^{k-\frac{\gamma(1-1/c)}{3}} + \sum_{i=0}^{\Order(\log n)} \min\{2^i, n^{\gamma/c}\} \mult T\!\left(\!m, \frac{n^{k-\gamma(1-1/c)}}{2^i}\!\right)\!\right)\!.
\end{equation*}

We will consider the following gap version of the $\VMin(\phi)$ problem: Along with the input, we are given an additional target $t$. The task is to compute an output satisfying the following requirements:

* If $\OPT \leq t$, then return “small” and attach a solution of value at most $c \mult t$.

* If $\OPT > c \mult t$, then return “large”.

* Otherwise, we do not care about the output.

An algorithm for this gap problem translates into an approximation algorithm for $\VMin(\phi)$ by using binary search on $t$ to determine $\OPT$ up to a factor of $c$. For that reason, we focus on the gap problem for the remainder of this proof.

Let $X_1, \ldots, X_k \subseteq \{0, 1\}^{|Y|}$ be the given gap instance with target $t$, and let $R$ and $S$ be parameters to be specified later. Throughout the algorithm, we maintain a global counter $L$ initialized to $L = 8n^{k-\gamma(1-1/c)} + 1$. The following steps are repeated $R$ times:

* Sample $S$ coordinates $y_1, \ldots, y_S \in Y$ uniformly at random. For a vector $x_i \in X_i$, we write $x_i'$ for the projected vector $(x_i[y_1], \ldots, x_i[y_S]) \in \{0, 1\}^S$ and we set $X_i' = \{ x_i' : x_i \in X_i \}$.

* List up to $L$ solutions to the $\VZero(\phi)$ instance $(X_1', \ldots, X_k')$. Afterwards, decrease $L$ by the number of detected solutions.

* For every tuple $(x_1', \ldots, x_k')$ listed in the previous step, check whether $\Val(x_1, \ldots, x_k) \leq c \mult t$. In that case, report “small” and attach $(x_1, \ldots, x_k)$.

If after all iterations no solution was detected, output “large”.

We start with the correctness argument. For a fixed round and a tuple $(x_1, \ldots, x_k)$, we distinguish two cases:

* If $\Val(x_1, \ldots, x_k) \leq t$, then: $\Pr\big[\Val(x_1', \ldots, x_k') = 0\big] \geq \big(1 - \frac t{|Y|}\big)^S =: p_1^S$.

* If $\Val(x_1, \ldots, x_k) > ct$, then: $\Pr\big[\Val(x_1', \ldots, x_k') = 0\big] \leq \big(1 - \frac{ct}{|Y|}\big)^S =: p_2^S$.

The strategy is to set $R$ large enough such that any (fixed) solution $(x_1, \ldots, x_k)$ of value at most $t$ is mapped to a tuple $(x_1', \ldots, x_k')$ of value zero in at least one round. It suffices to choose $R = p_1^{-S}$ as then the probability of failing in all $R$ rounds is bounded by $(1 - p_1^S)^R \leq 1/e$.

Next, we specify $S$ in such a way that the number of false positives – that is, tuples $(x_1', \ldots, x_k')$ of value zero whereas $(x_1, \ldots, x_k)$ has large value – is bounded by $\Order(m^{k-1})$ with good probability. Specifically, set

\begin{equation*}
S := \frac{\gamma\log n}{\log(1/p_2)} = \frac{\gamma\log n}{\log (1 - \frac{ct}{|Y|})^{-1}} \leq \frac{\gamma|Y| \log n}{ct}.
\end{equation*}

It follows that

\begin{equation*}
R = p_1^{-S} = \left(1 - \frac t{|Y|}\right)^{-S} \leq \left(1 - \frac t{|Y|}\right)^{\textstyle-\frac{\gamma|Y| \log n}{ct}} \leq n^{\gamma/c}.
\end{equation*}

The expected number of false positives among all rounds is therefore bounded by $R \mult n^k \mult p_2^S \le n^{\gamma/c} \mult n^k \mult n^{-\gamma} = n^{k-\gamma(1-1/c)}$. Using Markov's inequality, the number of false positives is at most $8n^{k-\gamma(1-1/c)}$ with probability at least $7/8$. Hence, it suffices to list $L = 8n^{k-\gamma(1-1/c)} + 1$ many solutions to all $\VZero(\phi)$ instances together, in order find at least one true positive with probability $1 - 1/e - 1/8 > 1/2$. By repeating the whole procedure $\Order(\log n)$ times, we amplify the success probability to $1 - n^{-\Omega(1)}$.

Finally, focus on the running time analysis. The first step runs in time $\Order(m)$ per round. The second and third steps are more involved. To achieve the claimed time bound, we have to implement the second step slightly more efficiently: Instead of running the listing algorithm with the global capacity $L$ directly, we use binary search to test for $2^i$ solutions, $i = 0, 1, \ldots, \log L$. If in the $i$-th iteration there are strictly less than $2^i$ solutions, we stop and continue as above. Among all $R$ rounds, we execute that $i$-th step at most $L / 2^i$ times. Hence, the running time of step 2 is bounded by

\begin{equation*}
\Order\!\left(\sum_{i=0}^{\log L} \min\left\{\frac{L}{2^i}, R\right\} \mult T(m, 2^i)\right) = \Order\!\left(\sum_{i=0}^{\log L} \min\{2^i, R\} \mult T\left(\!m, \frac{L}{2^i}\right)\right),
\end{equation*}

which is as stated, after plugging in the parameters from before. In the third step, across all rounds, we test at most $\Order(n^{k-\gamma(1-1/c)})$ tuples $(x_1, \dots, x_k)$ for their exact value $\Val(x_1, \dots, x_k)$. That task can be solved in time $\Order(m^{k-\gamma(1-1/c)/3})$ using <ref>.

In the following two corollaries, we show how to apply <ref> to obtain approximation schemes and constant-factor approximations.

Let $\phi$ be a Boolean function on $k$ inputs. If $\VZero(\phi)$ admits a listing algorithm in time $\Order(m^{k-\delta} \mult L^{\delta/k})$ for some $\delta > 0$, then there is a randomized algorithm computing a constant-factor approximation of $\VMin(\phi)$ in time $\Order(m^{k-\delta'})$ for some $\delta' > 0$.

We use <ref> with $\gamma = 1$ and some constant $c > k/\delta + 1$. The running time is bounded by

\begin{align*}
&\mathrel{\phantom=} \tilde\Order(m^{k-\frac{1-1/c}{3}} + n^{1/c} \mult m^{k-\delta} \mult (n^{k-(1-1/c)})^{\frac\delta k}) \\
&= \tilde\Order(m^{k-\frac{1-1/c}{3}} + m^{k-\frac\delta k + \frac{1 + \delta/k}c}) \\
&= \Order(m^{k-\delta'}),
\end{align*}

for $\delta' := \min\{\frac{1-1/c}3, \frac\delta k - \frac{1 + \delta/k}c\} > 0$.

Let $\phi$ be a Boolean function on $k$ inputs. If $\VZero(\phi)$ admits a listing algorithm in time $\tilde\Order(m^{k-\delta} + L)$ for some $\delta > 0$, then there is a randomized approximation scheme for $\VMin(\phi)$.

We use <ref> with $\gamma = \delta$ and $c = 1 + \varepsilon$, for an arbitrarily small constant $\varepsilon > 0$. The running time is bounded by

\begin{align*}
&\mathrel{\phantom=} \tilde\Order\!\left(m^{k-\frac{\delta(1-1/(1 + \varepsilon))}{3}} + \sum_{i=0}^{\Order(\log n)} \min\{2^i, n^{\delta/(1+\varepsilon)}\} \mult \!\left(\!m^{k-\delta} + \frac{n^{k-\delta(1-1/(1+\varepsilon))}}{2^i}\!\right)\!\right)\! \\
&= \tilde\Order(m^{k-\frac{\delta(1-1/(1 + \varepsilon))}{3}} + n^{\delta/(1 + \varepsilon)} m^{k-\delta} + n^{k-\delta(1-1/(1+\varepsilon))}) \\
&= \tilde\Order(m^{k-\frac{\delta(1-1/(1 + \varepsilon))}{3}}).
\end{align*}

Notice that indeed $\frac{\delta(1-1/(1+\varepsilon))}{3} > 0$.

It remains to show how to list solutions to $\VZero(\phi)$ fast enough to apply Corollaries <ref> and <ref>. First we give a general algorithm, which can be then directly applied with <ref> to yield <ref>:

Let $\phi$ be a Boolean function on $k$ inputs. If $\VZero(\phi)$ can be solved in time $\Order(m^{k-\delta})$ for some $\delta > 0$, then there is an algorithm listing $L$ solutions of $\VZero(\phi)$ in time $T(m, L) = \tilde\Order(m^{k-\delta} \mult L^{\delta/k})$.

Let $X_1, \ldots, X_k \subseteq \{0, 1\}^Y$ be the given input. We write $m(X_i)$ for the total number of ones in all vectors in $X_i$. Each set $X_i$ can be partitioned into sets $X_i = X_i^1 \union \{\hat x_i\} \union X_i^2$ where $m(X_i^1) < m(X_i) / 2$ and $m(X_i^2) < m(X_i) / 2$ in the following way: We greedily add elements to $X_i^1$ until $m(X_i^1) < m(X_i) / 2$ but $m(X_i^1 \union \{\hat x_i\}) \geq m(X_i) / 2$ for the next element $\hat x_i$. We take $\{\hat x_i\}$ to be a set on its own and set $X_i^2 = X_i \setminus (X_i^1 \union \{\hat x_i\})$.

We can list all solutions $(x_1, \ldots, x_k)$ involving one of the middle elements $\hat  x_i$ in time $\Order(m^{k-1})$ using the baseline algorithm. There are $2^k$ many subproblems remaining, where each is of the form $(X_1^{j_1}, \ldots, X_k^{j_k})$ for $j_1, \ldots, j_k \in \{1, 2\}$. Using the assumed efficient algorithm for $\VZero(\phi)$, we test for each of these instances whether it contains a solution. For each subproblem which is a YES instance, continue recursively. If at some point we reported more than $L$ solutions, stop.

Since we cannot miss solutions in the branching, the correctness is clear. For the running time, note that in each recursive call the sparsity was halved, and therefore the recursion depth is bounded by $\Order(\log m)$. Each individual call on the $i$-th recursion level takes time $\Order((m/2^i)^{k-\delta})$ and there are at most $\min\{L, 2^{ik}\}$ calls on that level. Hence, we can bound the total running time by

\begin{equation*}
T(m, L) \leq \sum_{i=0}^{\Order(\log m)} \min\{L, 2^{ik}\} \mult \Order((m/2^i)^{k-\delta}) \leq \tilde\Order(m^{k-\delta} L^{\delta/k}).
\end{equation*}

The last inequality holds because there are $\Order(\log m)$ summands and the largest one has $L = 2^{ik}$.

When $\phi$ has and-hardness $\Hand(\phi) \leq 1 < k$ we can improve upon <ref>:

Let $\phi$ be a Boolean function on $k$ inputs. If $\Hand(\phi) \leq 1 < k$, then there is an algorithm listing $L$ solutions of $\VZero(\phi)$ in time $T(m, L) = \tilde\Order(m^{k-1} + L)$.

This proof is similar to <cit.>. Let us start with the case $k = 2$; we later point out how to generalize. We distinguish several formulas $\phi$:

Case 0: $\phi$ has 0 or 4 satisfying assignments. Then $\phi$ trivially accepts or rejects every input and we can list $L$ solutions in time $\Order(L)$.

Case 1: $\phi$ has 1 satisfying assignment. This case is contradictory since $\Hand(\phi) \leq 1$.

Case 2: $\phi$ has 2 satisfying assignments.

Case 2a: $\phi(z_1, z_2) = (z_1 \leftrightarrow z_2)$ or $\phi(z_1, z_2) = (z_1 \centernot\leftrightarrow z_2)$.
In this case, any solution $(x_1, x_2)$ requires that either $x_1$ and $x_2$ are equal in every coordinate, or exactly negations of each other. In any case, for each vector $x_1$ there exists at most one choice $x_2$ such that $(x_1, x_2)$ is a solution. Thus, it is easy to list all solutions in time $\tilde\Order(m)$.

Case 2b: $\phi$ depends only on one input $z_i$. Without loss of generality, assume that $i = 1$. Then there can be at most one vector $x_1$ which participates in a solution. It takes time $\Order(m)$ to identify this vector and to list all solutions $(x_1, x_2)$, for all $x_2$.

Case 3: $\phi$ has 3 satisfying assignments. Then $\phi$ has only one falsifying assignment, say $(1, 1)$. That means that the only possible solution $(x_1, x_2)$ is that both $x_1$ and $x_2$ are the all-ones vector. It easy to check whether such a pair exists in time $\Order(m)$.

Let $\Phi = \{ \phi(z_1, z_2) : \Hand(\phi) \leq 1 \}$. By combining the previous cases, we can also list $L$ solutions of the hybrid problem $\VZero(\Phi)$ in time $\tilde\Order(m + L)$. Indeed, we can list all solutions for each individual nontrivial problem $\VZero(\phi)$ in time $\tilde\Order(m)$, and report only those solutions which are part of every individual solution set. There are two corner cases: If there are some coordinates associated to the constant $\false$-function, then we return no solution at all, and if all coordinates are associated to the constant $\true$-function, then we proceed as in Case 0.

Finally, assume that $k > 2$. We show how to list $L$ solutions to $\VZero(\phi)$. Since $\Hand(\phi) \leq 1$, there exists a set of $k - 2$ indices, say $\{3, \ldots, k\}$, which we can brute-force over, such that the remaining problem is exactly $\VZero(\Phi)$. For any tuple $(x_3, \ldots, x_k)$, we first compute the number of solutions $(x_1, x_2, x_3, \ldots, x_k)$ in time $\tilde\Order(m)$, using the same case distinction as before. Afterwards, we split our global budget $L$ in such a way that we never list too many solutions of $\VZero(\Phi)$, and run the previous listing algorithm for every tuple $(x_3, \ldots, x_k)$. The total running time is $\tilde\Order(n^{k-2} m + L) = \tilde\Order(m^{k-1} + L)$.

Finally, we put things together and prove the main result of this section:

The first bullet follows by combining <ref> and <ref>. The second bullet, and in particular the equivalence of $\VZero(\phi)$ and approximating $\VMin(\phi)$ within a constant factor, follows by combining <ref> and <ref>.

One might hope to give an approximation scheme for $\Hand(\phi) = 2$ in a similar way. Unfortunately, it is unlikely that a listing algorithm for $\VZero(\phi)$ in time $\tilde\Order(n^{k-\delta} + L)$ exists: There exists a fine-grained reduction from triangle detection to $\VZero(\phi)$ <cit.>, and thus we are implicitly also hoping for an output-linear triangle listing algorithm. However, previous work [72, 26] suggests that we cannot avoid a dependence on $L \mult \poly(n)$.

§ ADDITIVE APPROXIMATION ALGORITHMS

We say that an algorithm computes an additive $c$-approximation if it returns a solution whose value is contained in the interval $[\OPT - c, \OPT + c]$. Similarly as for multiplicative approximations, we can define approximation schemes in the additive setting.

Let $\psi$ be an $\OptSP_k$ formula. We say that $\Opt(\psi)$ admits an additive approximation scheme if, for any $\varepsilon > 0$, there exists some $\delta > 0$ and an algorithm computing an additive $\varepsilon |Y|$-approximation of $\Opt(\psi)$ in time $\Order(m^{k-\delta})$.

We say that $\Opt(\psi)$ admits an efficient additive approximation scheme if there exists some fixed constant $\delta > 0$, such that for any $\varepsilon > 0$ there exists an algorithm computing an additive $\varepsilon |Y|$-approximation of $\Opt(\psi)$ in time $\Order(m^{k-\delta})$.

The complexity landscape of multiplicative approximations turned out to be rich, featuring natural problems in all major regimes of approximation guarantees. In contrast, we draw a significantly simpler picture for additive approximations.

Let $\psi$ be an $\OptSP_k$ graph formula.

* There exists a randomized additive approximation scheme for $\Opt(\psi)$.

* If $3 \leq \Hdeg(\psi)$ or $\Hdeg(\psi) = k$, then there exists no efficient additive approximation scheme for $\Opt(\psi)$ unless the Sparse  hypothesis fails.

In summary, all problems $\Opt(\psi)$ admit approximation schemes, but no efficient ones (except for the problems that can be optimized exactly).

In this section we will show the first item of <ref>, i.e. that all problems $\Opt(\psi)$ admit additive approximation schemes. We defer the proof of the second item to <ref>. In particular, we will show the following:

Let $\phi$ be an arbitrary Boolean function. There exists a randomized additive approximation scheme for $\VOpt(\phi)$.

Combining <ref> with the equivalence of $\Opt(\psi)$ and vector problems $\VOpt(\psi)$ (which also holds for additive approximations, see <ref> for details), we obtain a proof for the algorithmic part of <ref>.

The techniques used to obtain multiplicative approximations often differed substantially for maximization and minimization. As it turns out, to obtain additive approximation schemes we can treat both in a unified way. Indeed, to prove <ref>, we demonstrate how to reduce every problem $\VOpt(\phi)$ to an instance of low-dimensional Maximum Inner Product (), or equivalently, low-dimensional Minimum Inner Product (). It is known that both  and  admit polynomial-time improvements in the low-dimensional regime using the polynomial method [11, 9]:

For every $c > 0$, there exists some $\delta > 0$ such that  on $d = c \log n$ dimensions can be solved in time $\Order(n^{2-\delta})$.

As a first algorithmic step, we establish a simple dimension reduction:

Let $\phi$ be an arbitrary Boolean function. For every $\varepsilon > 0$, there is a randomized linear-time reduction, turning a given an instance of $\VOpt(\phi)$ on $n$ vectors of dimension $d$ into another $\VOpt(\phi)$ instance on $n$ vectors of dimension $d' = \Order(\log n)$, such that with high probability we have $|\OPT / d - \OPT' / d'| \leq \varepsilon$, where $\OPT'$ is the optimal value of the constructed instance.

Set $d' := c \varepsilon^{-2} \log n$ for some sufficiently large constant $c$. Sample $d'$ coordinates from $Y$ uniformly and independently at random, and let $X_1', \ldots, X_k'$ be the projections of the input vectors to these $d'$ coordinates. For any $x_1' \in X_1', \ldots, x_k' \in X_k'$, we have that $\Val(x_1', \ldots, x_k')$ is a random variable with expectation $\Ex[\Val(x_1', \ldots, x_k')] = \frac{d'}{d} \Val(x_1,\dots,x_k)$. Moreover, since each coordinate was sampled independently and uniformly at random, by an additive Chernoff bound we have

\begin{equation*}
\Pr\left(\left|\frac{\Val(x_1,\dots,x_k)}{d} - \frac{\Val(x'_1,\dots,x'_k)}{d'}\right|
> \varepsilon\right) \leq 2 \exp(-2 \varepsilon^2 d') \leq \Order(n^{-2c}).
\end{equation*}

Thus, by a union bound over all tuples $(x_1, \ldots, x_k)$, it holds that $|\OPT / d - \OPT' / d'| \leq \varepsilon$ with probability $1 - n^{-\Omega(1)}$, where $\OPT'$ is the optimal value of the new instance. As claimed, we can construct the instance in time $\Order(m)$ by once iterating over all one-entries, after subsampling the $d'$ relevant coordinates.

Having applied the dimension reduction, we can complete the reduction from additively approximating $\VMax(\phi)$ to low-dimensional .

Let $\phi$ be an arbitrary Boolean function. There exists a randomized additive approximation scheme for $\VMax(\phi)$.

Let $(X_1, \ldots, X_k, Y)$ be the given $\VMax(\phi)$ instance, and fix $\varepsilon > 0$. In order to compute an additive $\varepsilon d$-approximation of $\VMax(\phi)$, we can assume that $d = |Y| = \Order(\log n)$ by applying <ref>. Our goal is to solve the resulting instance exactly by “covering” every satisfying assignment of $\phi$ by the all-ones assignment (which is satisfying for k). More precisely, let $\alpha_1, \ldots, \alpha_\ell \in \{0, 1\}^k$ denote the satisfying assignments of $\phi$. Let $Y' = Y \times [\ell]$ be a new set of dimensions and for each vector $x_i \in X_i$, we create a new vector $x_i' \in X_i'$ with

\begin{equation*}
x_i'[(y, j)] =
\begin{cases}
x_i[y] &\text{if $\alpha_j[i] = 1$,} \\
1 - x_i[y] &\text{otherwise.}
\end{cases}
\end{equation*}

It is easy to check that $\Val(x_1, \ldots, x_k) = \innerprod{x_1'}{\ldots, x_k'}$, and therefore it suffices to solve the k instance $(X_1', \ldots, X_k', Y')$. We brute-force over $k-2$ variables, and solve the remaining  instance using the assumed efficient algorithm (notice that indeed $d' = |Y'| = d \ell = \Order(\log n)$). The total running time is $\Order(n^{k-2} n^{2-\delta}) = \Order(n^{k-\delta}) = \Order(m^{k-\delta})$ for some $\delta > 0$.

Instead of proving an analogous reduction to from $\VMin(\phi)$ to , we instead show the following more general statement, which we will reuse in <ref> to rule out efficient additive approximation schemes.

Let $\phi$ be an arbitrary Boolean function. Via a randomized reduction, there exists an additive approximation scheme for $\VMax(\phi)$ if and only if there exists an additive approximation scheme for $\VMin(\phi)$. The same holds for efficient additive approximating schemes.

We focus only on one direction, the other one is analogous. Suppose there exists an additive approximation scheme for $\VMax(\phi)$, and fix some $\varepsilon > 0$. We can compute an additive $\varepsilon d$-approximation for a given $\VMin(\phi)$ instance $(X_1, \ldots, X_k, Y)$ on dimension-$d$ vectors using the following algorithm:

* Apply the dimension reduction from <ref> with parameter $\varepsilon / 2$ to obtain an equivalent $\VMin(\phi)$ instance $(X_1', \ldots, X_k', Y')$ on $d' = |Y'| = \Order(\log n)$ dimensions.

* Complement all vectors in $X_1', \ldots, X_k'$ to obtain a $\VMax(\phi)$ instance $(X_1'', \ldots, X_k'', Y')$.

* Use the assumed additive approximation scheme to compute an additive $\frac{\varepsilon d'}{2}$-approx-imation $V$ of the $\VMax(\phi)$ instance $(X_1'', \ldots, X_k'', Y')$, and return $d - \frac{d}{d'} V$.

Let $\OPT$ denote the optimal value of the original $\VMin(\phi)$ instance, and let $\OPT'$ and $\OPT''$ be the optimal values of the $\VMin(\phi)$ and $\VMax(\phi)$ instances computed in the second and third steps, respectively. The algorithm guarantees that $|\OPT'' - V| \leq \frac{\varepsilon d'}{2}$ and by construction it holds that $\OPT' = d' - \OPT''$. Moreover, with high probability the dimension reduction succeeds in which case $|\OPT - \frac{d}{d'}\OPT'| \leq \frac{\varepsilon d}{2}$. Plugging these three bounds together yields that $|\OPT - (d - \frac{d}{d'} V)| \leq \varepsilon d$.

Running the first step of the algorithm takes time $\Order(m)$ by <ref>. The complementation takes time $\tilde\Order(m)$, as the dimension was reduced to $d' = \Order(\log n)$. Finally, applying the additive approximation scheme for $\VMax(\phi)$ takes time $\tilde\Order(m^{k-\delta})$ for some $\delta > 0$, which dominates the total running time. If the $\VMax(\phi)$ additive approximation scheme is efficient, then so is the constructed one for $\VMin(\phi)$.

Finally, note that <ref> follows by combining <ref> and

§ HARDNESS OF APPROXIMATION

In this section, we give the proofs of our results for hardness of approximation. Recall that in the minimization case, <ref> immediately rules out the existence of multiplicative approximations for any $\psi$ with $\Hand(\psi) = k$ or $3 \leq \Hand(\psi) \leq k$. This was done by arguing that any approximation for $\VMin(\psi)$ is at least as hard as $\Zero(\psi)$, for which [31] gave a complete classification.

The maximization case is more complicated. To show hardness of approximation for maximization problems, we make use of the distributed PCP framework which was introduced in [7] and further developed in [74, 36, 60]. We use this as the main tool (<ref>) to give our results for hardness of approximation. In <ref> we address the hardest regime, giving the lower bound of <ref>. In <ref> we develop our main technical contribution and use it to rule out approximation schemes, completing the lower bound of <ref>. Finally, in <ref> we rule out efficient approximation schemes for both maximization and minimization problems, which gives the lower bounds for Theorems <ref> and <ref>.

§.§ Distributed PCP

All the hardness results in this section rely on the distributed PCP reduction. In a nutshell, this gives a reduction from $\kOV{k}$ in the low dimensional regime, i.e. $d = c \log n$ where $c$ is a constant, to a subpolynomial number of instances of $\kMaxIP{k}$ with dimension $\exp(c) \cdot \log n$ and introduces a gap in the optimal value of the instances depending on whether we started from a YES or a NO instance. In this way, an algorithm giving an approximation for $\kMaxIP{k}$ can distinguish between both cases and decide the original instance.

For our exposition, we extract the main properties of this reduction in the following lemma, which is the main technical tool that we will use. In <ref> we elaborate on how this can be derived as a simple combination of the results in [36] and [60], both of which make use of the key improvement of Rubinstein [74] over the basic reduction introduced in [7].

[[36, 60, 74]]lemmalemreductionclean
Let $\phi: \{0,1\}^k \to \{0,1\}$ have exactly one satisfying assignment.
There is a universal constant $c_1$ such that for every $c$ and parameters $0 < \gamma \leq 1, \tau \geq 2$, there is a reduction from k on sets of size $n$ and dimension $d = c \log n$, to $n^{\gamma}$ instances $I_1,\dots,I_{n^{\gamma}}$ of $\VMax(\phi)$, each on $d'$ dimensions and with sparsity $m'$. Let $T := c \log n \cdot \tau^{c_1}$. Then, the reduction has the following properties:

* $d' = \tau^{\poly(k, c/\gamma)} \cdot \log n$ and $m' \leq n d'$.
Completeness: If we start from a YES instance of $\kOV{k}$, then there is some $j \in [n^{\gamma}]$ such that in $I_j$, it holds that $\OPT = T$.
Soundness: If we start from a NO instance of $\kOV{k}$, then $\OPT \leq T / \tau$ for all instances $I_1,\ldots,I_{n^\gamma}$.

The running time of the reduction is linear in the output size: $\Order(n^{1+\gamma}d')$.

§.§ Hardness for Hand(phi) = k

In this section we give a proof of the lower bound part of <ref>.

Let $\phi: \{0,1\}^k \to \{0,1\}$ have and-hardness $\Hand(\phi) = k$. Then for all $\delta > 0$ there is an $\varepsilon > 0$ such that there is no $m^{\varepsilon}$-approximation for $\VMax(\phi)$ in time $\Order(m^{k - \delta})$ unless the low-dimensional k hypothesis fails.

Assume for contradiction that there is a $\delta > 0$ such that for all $\varepsilon > 0$ there is an algorithm $\calA$ which gives an $m^{\varepsilon}$-approximation to $\VMax(\phi)$ in time $\Order(m^{k-\delta})$. We will show that by appropriately setting the parameters of the reduction in <ref>, we can reduce any $\kOV{k}$ instance on $d = \Theta(\log n)$ to $n^\gamma$ instances of $\VMax(\phi)$ introducing a gap in the optimal value of $\tau = (m')^{\varepsilon}$, where $m'$ is the sparsity of the constructed instances of $\VMax(\phi)$. By making $\gamma$ small enough and ensuring that $m' \leq n^{1 + \beta}$ for some small constant $\beta > 0$, we can thus decide the $\kOV{k}$ instance by running $\calA$ on the constructed instances, in time $\Order(n^{\gamma}\cdot (n^{1+\beta})^{k - \delta}) = \Order(n^{k - \delta'})$ for some $\delta' > 0$, which contradicts the low-dimensional k hypothesis.

Now we give the full details. By <ref>, note that $\Hand(\phi) = k$ if and only if $\phi$ has exactly one satisfying assignment, so we can use <ref>. Set $\beta := \delta/(3k)$. Then, for every constant $c > 0$, we apply Lemma <ref> with parameters $\gamma := \delta/3$ and $\tau := (n^{1+\beta})^{\varepsilon}$ to reduce any instance of k on $d = c \log n$ dimensions, to $n^{\gamma}$ instances of $\VMax(\phi)$ on $d' = \tau^{\poly(k, c/\gamma)} \cdot \log n$ dimensions each.

Note that by setting $\varepsilon < \frac{\beta}{(1+\beta)\cdot \poly(k, c/\gamma)}$, we can bound $d' \leq n^{\beta}$ and further, the sparsity of the constructed instances by $m' \leq n^{1+\beta}$. Since by assumption $\calA$ computes an $(m')^{\varepsilon} \leq (n^{1+\beta})^\varepsilon = \tau$/̄approximation, we can decide the original $\kOV{k}$ instance by running $\calA$ on the constructed instances. This takes time

\begin{equation*}
\Order(n^{\gamma} \cdot (m')^{k - \delta})
=  \Order(n^{\gamma} \cdot (n^{1+\beta})^{k-\delta})
= \Order(n^{k + \beta k - \delta + \gamma})
= \Order(n^{k + \delta/3 - \delta + \gamma})
= \Order(n^{k - \gamma}).
\end{equation*}

Since the time needed to run the reduction is $\tilde\Order(n^{1 + \gamma})$, we obtain an algorithm to decide the $\kOV{k}$ instance in time $\Order(n^{k - \gamma})$. This contradicts the low-dimensional k hypothesis.

§.§ Hardness for 3 <= Hand(phi) < k

If $\Hand(\phi) = \Hdeg(\phi) = k$, then <ref> rules out even the existence of subpolynomial multiplicative approximations for $\VMax(\phi)$. But consider the case when $3 \leq \Hand(\phi) < k$: By <ref> we know that $\VMax(\phi)$ admits some constant approximation, but how small can the approximation factor be? In particular, can we hope to get an approximation scheme? In this section we answer this negatively by showing that any such function $\phi$ cannot be approximated within $(1 - \binom k3{}^{-1} + \varepsilon)^{-1}$ in time $\Order(m^{k-\delta})$ for any $\varepsilon > 0$ and $\delta > 0$, assuming the Sparse  hypothesis. In other words, we can rule out approximation schemes for all such $\phi$'s.

Our reduction is outlined in <ref>. At a high level there are two main steps: we first introduce an intermediate problem that we call $\kOV{(k,3)}$ and show that it is hard in the low-dimensional regime assuming the Sparse  Hypothesis (<ref>). We then give a gap introducing reduction from $\kOV{(k,3)}$ to $\VMax(\phi)$ by using the distributed PCP reduction as a blackbox (<ref> and <ref>).[We note that an alternative to our reduction is to reduce  to $\kExactIP{(k,3)}$, and then reduce $\kExactIP{(k,3)}$ to approximate $\VMax(\phi)$ using the distributed PCP. Although this is slightly more direct, it requires to show that the Disjointness protocol used in the distributed PCP can be extended for the more general $\kExactIP{k}$. Moreover, we think the reduction via $\kOV{(k, 3)}$ provides a conceptually clean and natural abstraction that might inspire future applications.]

We start by formally defining our intermediate problems:

Given sets of $n$ vectors $X_1, \ldots, X_k \subseteq \{0, 1\}^d$, where to each coordinate $y \in [d]$ we associate three active indices $a, b, c \in [k]$, detect if there are vectors $x_1 \in X_1, \ldots, x_k \in X_k$ such that for all $y \in [d]$, it holds that $x_a[y] \mult x_b[y] \mult x_c[y] = 0$ where $a, b, c$ are the active indices at $y$.

In the same spirit, we also define the “$(k,3)$-” problems for $\kMaxIP{k}$ and k: Here, let the value $\Val(x_1, \dots, x_k)$ denote the number of coordinates $y \in [d]$ with $x_a[y] \mult x_b[y] \mult x_c[y] = 1$, where again $a, b, c$ are the active indices at $y$. Then the (k,3) problem is to maximize the value among all vectors $x_1, \dots, x_k$, and the (k,3) problem is to check whether there exist vectors $x_1, \dots, x_k$ of value equal to a given target.

§.§.§ Hardness of Low-Dimensional (k,3)-OV

As mentioned earlier, the first step in the reduction it to show that we can reduce a sparse instance of  to an instance of $\kOV{(k,3)}$ with dimension $d = \Theta(\log n)$. We proceed by first reducing $\MAXThreeSAT$ to $\kExactIP{(k,3)}$, and then make use of the following known reduction from $\kExactIP{3}$ to $\kOV{3}$:

For all constants $c > 0$ and $\gamma > 0$, there is a reduction from $\kExactIP{3}$ with target $\beta$ on $n$ vectors and dimension $d = c \log n$ to $n^{\gamma \log(c/\gamma)}$ instances $I_1,\dots,I_{n^{\gamma \log(c/\gamma)}}$ of $\kOV{3}$ on $n$ vectors and dimension $d' = \Order(2^{c/\gamma} \cdot \log n)$ with the following properties:

* Each vector in the $\kExactIP{3}$ is in one-to-one correspondence with a vector in each of the constructed instances.
Completeness: If we start from a YES instance of 3, then there exists a $j \in [n^{\gamma \log(c/\gamma)}]$ such that $I_j$ is a YES instance of 3.
Soundness: If we start from a NO instance of $\kExactIP{3}$, then for all $j \in [n^{\gamma \log(c/\gamma)}]$, $I_j$ is a NO instance.

The running time of the reduction is linear in the output size: $\tilde\Order(n^{1+\gamma \log(c/\gamma)})$.

For every $\delta > 0$, there exists some $c > 0$ such that (k,3) in dimension $d = c \log n$ cannot be solved in time $\Order(n^{k-\delta})$, unless the Sparse  hypothesis fails.

Take an instance $\Phi$ of $\MAXThreeSAT$ on $N$ variables and $M = c N$ clauses. As a first step, we reduce to $O(N)$ instances of $\kExactIP{(k, 3)}$ using the split-and-list technique due to Williams [78]: We split the variables into $k$ groups, and let $V_1,\dots,V_k$ be the sets of partial assignments to each group, i.e. $|V_i| = 2^{N/k}$. Given a partial assignment $v_i \in V_i$, we construct a vector $x_i \in \{0,1\}^{M}$ and assign its entries as $x_i[j] = 0$ if and only if $v_i$ contains a literal which satisfies the clause $C_j$. In this way, we obtain $k$ sets of vectors $X_1,\dots,X_k$ with $n := |X_i| = 2^{N/k}$ and dimension $d = M = c N = c \cdot k \log n$. For each coordinate $j \in [d]$ we say that the set $X_i$ is active in dimension $j$ iff its corresponding group contains a variable inside the clause $C_j$. Since we start from a $\MAXThreeSAT$ instance, each dimension has at most 3 active sets. The key property is that for an assignment $x_1,\dots,x_k$, we have that $d - \langle x_1,\dots,x_k \rangle$ counts the number of satisfied clauses. Moreover, in each dimension, the inner product only depends on the active vectors (a set $X_i$ that is not active for a given clause $C_j$ has $x_i[j] = 1$ for all $x_i \in X_i$). Thus, we can decide the $\MAXThreeSAT$ instance, by deciding $d$ instances of $\kExactIP{(k,3)}$: we try all $d$ possible target values and output $d$ minus the minimum. Note that the way we defined $\kExactIP{(k,3)}$
requires exactly 3 active sets per dimension, while in this reduction we have at most 3. To fix this, if some dimension has $a < 3$ active sets, we select $3 - a$ other arbitrary sets as active. The instance remains equivalent since for that dimension all vectors in the newly active sets will have a one.

Next, we use <ref> to reduce each of the $d$ instances of $\kExactIP{(k,3)}$ to $\kOV{(k,3)}$: Fix an instance $X_1,\dots,X_k$ of $\kExactIP{(k,3)}$ with target $\beta$. For each $\{a,b,c\} \in \binom{[k]}3$, we project $X_a, X_b, X_c$ to the dimensions where $\{a,b,c\}$ are active. Let $X'_a, X'_b, X'_c$ be the resulting sets. Then, for each $\alpha \in [\beta]$, we can see $(X'_a,X'_b,X'_c)$ with target $\alpha$ as a $\kExactIP{3}$ instance. For each of these, we apply the reduction in <ref>, and obtain a collection of $\kOV{3}$ instances. We extend them to instances of $\kOV{(k,3)}$ by making the sets corresponding to $X_a,X_b,X_c$ active in all dimensions, and adding the sets $X_j$ for $j \in  [k] \setminus \{a,b,c\}$ with $n$ zero-vectors each (i.e. we add dummy vectors for each non-active set, which are irrelevant for the instance). We denote the resulting collection of $\kOV{(k,3)}$ instances by $\calI_{\{a,b,c\}}$. By the properties of <ref>, we have that $|\calI_{\{a,b,c\}}| \leq \beta \cdot n^{\gamma \log (c/\gamma)} = \Order(n^{\gamma \log(c/\gamma)}\log n)$ for all $\{a,b,c\} \in \binom{[k]}3$, and the dimension of each instance is $\Order(2^{c/\gamma} \log n)$. As a final step, we combine the $\calI$'s into $\Order(n^{\binom k3 \gamma \log(c/\gamma)} \log n)$ instances of $\kOV{(k,3)}$ in the natural way: for each combination of $(I_1,\dots,I_{\binom k3}) \in \calI_{1} \times \dots \times \calI_{\binom k3}$ (where we consider all $\{a,b,c\} \in \binom{[k]}3$ in some fixed order), we construct an instance of $\kOV{(k,3)}$ by concatenating the $\binom k3$ vectors corresponding to the original $\kExactIP{(k,3)}$ instance (note that in each $I_j$, there is a one-to-one correspondence between vectors in the original and the reduced instances) and summing up the targets (we discard any constructed instance not summing up to $\beta$).

In summary, we reduced the given $\MAXThreeSAT$ instance $\Phi$ of $N$ variables and $cN$ clauses to $\tilde\Order(n^{\binom k3\gamma \log(c/\gamma)})$ instances of $\kOV{(k,3)}$ with dimension $d' = \Order(\binom k3 2^{c / \gamma} \log n)$. By the completeness and soundness of <ref>, we can decide $\Phi$ by checking whether any of the constructed $\kOV{(k,3)}$ instances is a YES-instance. Thus, assume for contradiction that there is an algorithm $\calA$ and some $\delta > 0$ such that for all $c'$, $\calA$ decides $\kOV{(k,3)}$ on $d = c' \log n$ dimensions in time $\Order(n^{k - \delta})$. Then, by picking $\gamma$ sufficiently small we can make $\gamma \binom k3 \log(c/\gamma) < \delta/2$. Since the dimension of the $\kOV{(k,3)}$ instances is $d' = \Order(\binom k3 2^{c / \gamma} \log n) = \Order(\log n)$, we can solve the $\MAXThreeSAT$ by running $\calA$. This takes time

\begin{equation*}
\tilde\Order(n^{\binom k3\gamma\log(c / \gamma)} \cdot n^{k - \delta}) = \tilde\Order(n^{k - \delta/2}).
\end{equation*}

Since $n = 2^{N/k}$, this gives a $\MAXThreeSAT$ algorithm in time $\Order(2^{N(1 - \delta/(2k))})$, contradicting the Sparse $\MAXThreeSAT$ hypothesis.

§.§.§ Gap Reduction from Low-Dimensional (k,3)-OV to VMax(phi)

Having established the hardness of $\kOV{(k,3)}$ in the low-dimensional regime, we will use the distributed PCP reduction from <ref> to show hardness of approximation for $\VMax(\phi)$ when $\Hand(\phi) \geq 3$. As an intermediate step we will need the following reduction:

Let $\phi : \{0,1\}^k \to \{0,1\}$ have and-hardness $3 \leq \Hand(\phi) \leq k$. Then, given an instance of $\kMaxIP{(k,3)}$ on $n$ vectors of dimension $d$, there is a reduction to $\VMax(\phi)$ on $n$ vectors of dimension $d$ such that the value of any solution $x_1, \dots, x_k$ in the original instance is the same as the value of the corresponding solution $x_1', \dots, x_k'$ in the constructed instance. The reduction runs in time $\Order(nd)$.

For each coordinate $y \in [d]$, the $\kMaxIP{(k,3)}$ instance has three active indices $a_y, b_y, c_y$. By definition of $\Hand(\phi)$, there is an $S = \{a_y, b_y, c_y\}$-restriction $\phi'$ of $\phi$ which has a unique satisfying assignment. Let $\alpha_y : [k] \setminus S \to \{0,1\}$ be the partial assignment which restricts $\phi$ to $\phi'$, and denote the satisfying assignment by $\beta_y: S \to \{0,1\}$.

For every $j \in [k]$ and all $x_j \in X_j$, we create a vector $x'_j \in X'_j$ in the $\VMax(\phi)$ instance, and set the entries for each coordinate $y \in [d]$ as follows:

\[
x'[y] :=
\begin{cases}
\alpha_y(j) & \text{if $j \notin \{a_y, b_y, c_y\}$,} \\
\beta_i(j) & \text{if $j \in \{a_y, b_y, c_y\}$ and $x_y[j] = 1$,} \\
1 - \beta_i(j) & \text{otherwise.}
\end{cases}
\]

It is immediate that the $\VMax(\phi)$ instance has the same number of vectors and the same dimension as the original instance. Moreover, the value of each possible solution is the same in both instances. The running time is $\Order(nd)$.

Next, we give a gap introducing reduction from low-dimensional (k,3) to $\VMax(\phi)$. The steps are similar to those in the proof of <ref>:

Let $\phi: \{0,1\}^k \to \{0,1\}$ have hardness $3 \leq \Hand(\phi) \leq k$. Then, there is a universal constant $c_1$ such that for every $c > 0$, and parameters $0 < \gamma \leq 1$ and $\tau \geq 2$, there is a reduction from (k,3) in dimension $c \log n$ to $n^{\gamma}$ instances $I_1,\dots,I_{n^{\gamma}}$ of $\VMax(\phi)$. For $T := c \log n \cdot \tau^{c_1}$, the following properties hold:

* The constructed $\VMax(\phi)$ instances have dimension $d' = \binom k3\cdot \tau^{\poly(k,c/\gamma)} \log n$, and sparsity $m' = \Order(n \cdot \tau^{\poly(k, c/\gamma)}\log n)$.
Completeness: If we start from a YES instance of $\kOV{(k,3)}$, then there is some $j \in [n^{\gamma}]$ such that in $I_j$ it holds that $\OPT = \binom k3 \cdot T$.
Soundness: If we start from a NO instance of $\kOV{(k,3)}$, then for every $I_j$, $j \in [n^{\gamma}]$ we have that $\OPT \leq (\binom k3 - 1) \cdot T + T/\tau$.

The running time of the reduction is linear in the output size: $\tilde\Order(n^{1 + \gamma})$.

Let $X_1,\dots,X_k$ be the input instance of $\kOV{(k, 3)}$ in $d = c \log n$ dimensions. As a first step, we make sure that for all $\{a,b,c\} \in \binom{[k]}3$, there is at least one dimension in which $\{a,b,c\}$ are active, by adding a fresh dimension with all zeros for all vectors if necessary.

Now we describe the reduction. For each $\{a,b,c\} \in \binom{[k]}3$, we project $X_a, X_b, X_c$ to the dimensions where $\{a,b,c\}$ `are active. Let $X'_a, X'_b, X'_c$ be the resulting sets and note that we can see it as a $\kOV{3}$ instance. We pad the vectors with zeros, so that the dimension of this $\kOV{3}$ instance is also $d = c \log n$. Next, we invoke the reduction from <ref> on $X'_a, X'_b, X'_c$ with parameters $\gamma' := \gamma / \binom k3$ and $\tau' := \tau$. This produces $n^{\gamma'}$ instances of $\kMaxIP{3}$, which we extend to instances of $\kMaxIP{(k, 3)}$ by adding zeros to the sets $X_j$'s for $j \in [k] \setminus \{a,b,c\}$ (i.e. we put zero-vectors corresponding to each vector from the non-participating sets). We denote by $\calI_{\{a,b,c\}}$ the collection of $n^{\gamma'}$ constructed instances of $\kMaxIP{3}$.

Having constructed $\calI_{\{a,b,c\}}$ corresponding to each $\{a,b,c\} \in \binom{[k]}3$, we merge them into $n^{\gamma' \cdot \binom k3} = n^{\gamma}$ instances of $\kMaxIP{(k,3)}$ as follows.  For each $(I_1,\dots,I_{\binom k3}) \in \calI_{1} \times \dots \times \calI_{\binom k3}$ we construct one instance of $\kMaxIP{(k,3)}$ in the natural way: Each $I_j$ has a vector associated to every $x_i \in X_i$ from the original $\kOV{(k,3)}$ instance, so we concatenate the $\binom k3$ copies across the $I$'s. This gives an instance of $\kMaxIP{(k,3)}$ with the same number of vectors as the original instance, dimension $d' = \binom k3 \cdot \tau^{\poly(k, c/\gamma)} \log n$. and sparsity $m' = \Order(n \cdot d')$.

As a final step, we apply <ref> to each of the $n^{\gamma}$ instances of $\kMaxIP{(k,3)}$ and obtain $n^{\gamma}$  instances of $\VMax(\phi)$, each with sparsity $m' = \Order(n \cdot d') = \Order(n \cdot \tau^{\poly(k, c/\gamma)}\log n)$. Now we analyze the completeness and soundness of the reduction:

Completeness: If $X_1,\dots,X_k$ is a YES instance of $\kOV{(k,3)}$, then there are vectors $x_1 \in X_1, \dots, \allowbreak x_k \in X_k$ such that $\langle x'_a, x'_b, x'_c \rangle = 0$ in the corresponding projected $\kOV{3}$ instances $X'_a,X'_b,X'_c$ for all $\{a, b, c\} \in \binom{[k]}3$. By the completeness of the reduction in <ref>, for each $\{a,b,c\} \in \binom k3$, in at least one of the $n^{\gamma'}$ instances of $\kMaxIP{3}$ the vectors corresponding to $x'_a, x'_b, x'_c$ attain a value of $T$. In particular, in at least one of the $n^{\gamma}$ final instances of $\VMax(\phi)$, the value of the vectors corresponding to $x_1,\dots,x_k$ is at least $\binom k3 \cdot T$.

Soundness: If $X_1,\dots,X_k$ is a NO instance, then for all $x_1 \in X_1, \dots, x_k \in X_k$, there is at least one $\{a,b,c\} \in \binom{[k]}3$ such that $\langle x'_a, x'_b, x'_c \rangle > 0$ in the corresponding projected $\kOV{3}$ instance $X'_a,X'_b,X'_c$. Hence, by the soundness of the reduction in <ref>, in all the final instances of $\VMax(\phi)$, the value attained by the vectors corresponding to $x_1,\dots,x_k$ is at most $(\binom k3 - 1)\cdot T + T / \tau$.

The running time is dominated by constructing the $n^{\gamma}$ instances of $\kMaxIP{(k,3)}$, which takes time $\tilde\Order(n^{1 + \gamma})$.

Finally, we are ready to give the main result, which proves the lower bound of <ref>:

Let $\phi: \{0,1\}^k \to \{0,1\}$ have and-hardness $3 \leq \Hand(\phi) \leq k$. Then, for all $0 < \varepsilon < \binom k3{}^{-1}$ and for all $\delta > 0$, we cannot compute a 0pt[0pt][0pt]$(1 - \binom k3{}^{-1} + \varepsilon)^{-1}$-approximation for $\VMax(\phi)$ in time $\Order(m^{k - \delta})$ unless the Sparse $\MAXThreeSAT$ hypothesis fails.

Suppose for contradiction there is some 0pt[0pt][0pt]$0 < \varepsilon < \binom k3{}^{-1}$ and $\delta > 0$ such that there is an algorithm $\calA$ computing a multiplicative $(1 - \binom k3{}^{-1} + \varepsilon)^{-1}$-approximation for $\VMax(\phi)$ in time $\Order(m^{k - \delta})$. We will show that by applying <ref>, we can use $\calA$ to decide any low-dimensional (k,3) instance in time $\Order(n^{k-\delta'})$ for some $\delta' > 0$, which would contradict the Sparse  hypothesis.

For every constant $c > 0$, we invoke the reduction from <ref> with parameters $\gamma := \delta / 2$ and $\tau > (\varepsilon \binom k3)^{-1}$ to reduce a (k,3) instance on $n$ vectors of dimension $c \log n$ to $n^{\gamma}$ instances of $\VMax(\phi)$ each with sparsity $m' = \Order(n \tau^{\poly(k, c/\gamma)} \log n) = \Order(n \log n)$.

By the soundness and completeness of the reduction, a $(1 - \binom k3{}^{-1} + \varepsilon)^{-1}$-approximation is sufficient to distinguish between the two cases:

\[
\Bigg(1 - \binom k3^{\!-1}\! + \varepsilon\Bigg) \cdot \binom k3 \cdot T >
\left(\binom k3 - 1\right)\cdot T + T / \tau.
\]

Thus, we can decide the original $\kOV{(k,3)}$ instance by running the reduction and using $\calA$ on the constructed instances. The time to run the reduction is $\tilde\Order(n^{1 + \gamma})$, and running $\calA$ on $n^{\gamma}$ instances of $\kMaxIP{(k,3)}$ with sparsity $m' = \Order(n \log n)$ takes time $\Order(n^\gamma \mult (m')^{k-\delta}) = \tilde\Order(n^{k+\gamma-\delta})$. Thus, by choosing $\gamma = \delta / 2$, the total running time is bounded by $\tilde\Order(n^{k-\gamma})$. By <ref>, this contradicts the Sparse  hypothesis.

§.§ Ruling out Efficient Approximation Schemes

Recall that we say that $\VOpt(\phi)$ admits an efficient approximation scheme, if there is a fixed $\delta > 0$ such that for any $\varepsilon > 0$, an $\varepsilon$-approximation can be computed in time $O(m^{k-\delta})$. In this section we rule out the existence of efficient approximation schemes for all problems which cannot be solved exactly, namely, for all problems $\VOpt(\phi)$ with $3 \leq \Hdeg(\phi)$ or $\Hdeg(\phi) = k$, thereby proving the lower bounds in <ref> and <ref>. Since a multiplicative approximation scheme implies an additive one, it suffices to show the result for the additive case. Moreover, by <ref>, we know that an additive approximation scheme for $\VMax(\phi)$ is equivalent to an additive approximation scheme for $\VMin(\phi)$, so we focus on the minimization case.

For $h \geq 3$, consider the natural generalization (k,h) of the (k,3) problem defined in <ref>. The main ingredient for our results is the following lemma, which shows that an additive approximation for $\kMaxIP{(k,h)}$ can be obtained from an additive approximation for $\VMin(\phi)$, when $\Hdeg(\phi) = h$.

Let $\phi: \{0,1\}^k \to \{0,1\}$ have degree hardness $\Hdeg(\phi) = h$. If $\VMin(\phi)$ has an additive approximation scheme, then for any $\varepsilon > 0$, there exists some $\delta > 0$ such that (k,h) has an additive $\varepsilon d$-approximation in time $\Order((nd)^{k-\delta})$.

Let $X_1,\dots,X_k \subseteq \{0,1\}^d$ be the $\kMaxIP{(k,h)}$ instance. We describe how to construct an instance $X'_1,\dots,X'_k \subseteq \{0,1\}^{O(d)}$ of $\VMin(\phi)$. For each coordinate $y \in [d]$, let $S_y \in \binom{[k]}h$ denote the set of active indices at $y$. Since $\phi$ has degree hardness $\Hdeg(\psi) = h$, there is an $S_y$-restriction $\phi_y$ of $\phi$ such that $\deg(\phi_y) = h$. Let $\alpha_y : [k] \setminus S_y \to \{0, 1\}$ denote the partial assignment which restricts $\phi$ to $\phi_y$. By <ref> there is a coordinate gadget for $\phi_y$, consisting of functions $\phi_{y,1}, \dots, \phi_{y,\ell}$ with constants $\beta^y_1, \beta^y_2 > 0$. For $j \in [\ell]$, let $\tau_{j,1},\dots,\tau_{j,k}$ denote the unary functions needed to transform $\phi_y$ into $\phi_{y,j}$. For every $i \in [k]$ and $x_i \in X_i$ we introduce $\ell$ new coordinates $x'_i[(y,1)],\dots,x'_i[(y,\ell)]$ and to be set as follows:

\begin{equation*}
x'_i[(y, j)] :=
\begin{cases}
\alpha_y(i) & \text{if $i \notin S_y$,} \\
\tau_{j,i}(x_i[y]) & \text{otherwise.}
\end{cases}
\end{equation*}

Note that we can make the constants $\beta^y_2$ the same for all $y \in [d]$: Let $\beta^*_2$ be the lowest common multiple of all the $\beta^y_2$'s. Then, by concatenating the $y$-th coordinate gadget $\beta^*_2 / \beta^y_2$ many times, we obtain $\beta^*_2$ for all $y \in [d]$. Thus, letting $\beta^*_1 := \sum_{y \in [d]} \beta^y_1$ and $\beta^*_2$ as indicated, we have that

\[
\Val(x'_1,\dots,x'_k) = \sum_{y \in [d]} \Bigg(\beta^y_1 - \beta^y_2 \prod_{i \in S_y} x_i[y]\Bigg) = \beta^*_1 - \beta^*_2 \cdot \Val(x_1,\dots,x_k).
\]

Let $d' = O(d)$ be the dimension of the constructed instance $X'_1,\dots,X'_k$ of $\VMin(\phi)$ and let $\OPT'$ be its optimal value. Let $\OPT$ be the optimal for the original instance $X_1,\dots,X_k$ of (k,h). Since $\beta^*_1, \beta^*_2 > 0$, we have that $\OPT' = \beta^*_1 - \beta^*_2 \cdot \OPT$. Thus, given an additive $\varepsilon d'$-approximation $V'$ for $\VMin(\phi)$, we compute $V := -(V' - \beta^*_1) / \beta^*_2 \in [\OPT - \varepsilon/\beta^*_2 \cdot d', \OPT]$, which is an additive $\Order(\varepsilon d)$-approximation for (k,h).

Since the reduction takes time $O(nd)$ and the produced instance is of size $m = O(nd)$, the result follows.

Note that if $h = k$ in <ref>, then the $\kMaxIP{(k,k)}$ is the same as the standard k and the result still applies.

Now we are ready to give the lower bounds. We start with the hardest regime, i.e., when $\Hdeg(\phi) = k$.

Let $\phi: \{0,1\}^k \to \{0,1\}$ have degree hardness $\Hdeg(\phi) = k$. Then, for all $\delta > 0$ there is some $\varepsilon > 0$ such that there is no additive $\varepsilon d$-approximation for $\VMin(\phi)$ in time $\Order(m^{k - \delta})$ unless the low-dimensional k hypothesis fails.

Suppose there is a $\delta > 0$ and an algorithm $\calA$ computing an additive $\varepsilon d$-approximation for $\VMin(\phi)$ in time $\Order(m^{k - \delta})$ for any $\varepsilon > 0$. We will show how to use <ref> in combination with <ref> to reduce any k instance in dimension $c \log n$ to a small number of $\VMin(\phi)$ instances for which we can use $\calA$ to decide the original instance in time $\Order(n^{k-\delta'})$ for some $\delta' > 0$.

For every constant $c > 0$, we apply Lemma <ref> with parameters $\gamma$ (to be set) and $\tau := 2$ to reduce an instance of k in dimension $d = c \log n$ to $n^{\gamma}$ instances of $\kMaxIP{k}$ on $d' = 2^{\poly(k, c/\gamma)} \log n = \Order(\log n)$ dimensions each. By the properties of Lemma <ref>, if we started from a YES instance, then at least one of the constructed $\kMaxIP{k}$ instances achieves a value of $T = c \cdot 2^{c_1} \log n$. Otherwise, all instances have value at most $T/2$. Thus, if we set $\varepsilon$ such that $\varepsilon \cdot d' \leq T/6$, an additive $\varepsilon d'$-approximation can distinguish the two cases. Since $d' = 2^{\poly(k, c/\delta)}\log n$, choosing $\varepsilon < \frac{c \cdot 2^{c_1}}{6 \cdot 2^{\poly(k, c/\gamma)}}$ suffices.

By <ref>, there exists some $\delta' > 0$ such that we can compute such an additive $\varepsilon d'$-approximation using $\calA$ in time $\Order((nd')^{k-\delta'})$. In this way, we can decide the $\kOV{k}$ instance by constructing the $n^{\gamma}$ instances of $\kMaxIP{k}$ instances in time $\tilde\Order(n^{1+\gamma})$ and computing the additive $\varepsilon d'$-approximation using $\calA$. The overall running time is

\begin{equation*}
\tilde\Order(n^{1 + \gamma} + n^{\gamma} \cdot ((nd') + (nd')^{k - \delta'})) = \tilde\Order(n^{k + \gamma - \delta'}).
\end{equation*}

By picking $\gamma < \delta'$, this contradicts the low-dimensional k hypothesis.

Finally we show the analogous result for $\VMin(\phi)$ with $3 \leq \Hdeg(\phi) \leq k$. Note that the proof is virtually the same as for <ref>, but we use the stronger Sparse  hypothesis, and the machinery developed in <ref>.

Let $\phi: \{0,1\}^k \to \{0,1\}$ have degree hardness $3 \leq \Hdeg(\phi) \leq k$. Then, for all $\delta > 0$, there is some $\varepsilon > 0$ such that there is no additive $\varepsilon d$-approximation for $\VMin(\phi)$ in time $\Order(m^{k - \delta})$ unless the Sparse  hypothesis fails.

Suppose there exists some $\delta > 0$ and an algorithm $\calA$ such that for any $\varepsilon > 0$, it produces an additive $\varepsilon d$-approximation for $\VMin(\phi)$ in time $\Order(m^{k - \delta})$. We will show how to use the gap introducing reduction from <ref> to reduce any (k,3) instance in dimension $c \log n$ to a few instances of (k,h), and then use $\calA$ is to distinguish the gap via <ref>.

For every constant $c$, we use <ref> with parameters $\gamma$ (to be set) and $\tau := 2$ to reduce an instance of (k,3) in dimension $d = c \log n$ to $n^{\gamma}$ instances of (k,3) each in dimension $d' = \tau^{\poly(k, c/\gamma)}\log n$ and with sparsity $m' = \Order(n \tau^{\poly(k, c/\gamma)} \log n) = \Order(n \log n)$. Note that we can further reduce each of these instances to (k,h), for any $3 < h \leq k$: For each coordinate we add $h-3$ arbitrary active indices and set all entries for these indices to one. The produced (k,h) instances are clearly equivalent since in each coordinate the contribution to the objective only depends on the 3 active sets in the original (k,3) instance.

To decide the (k,3) instance, we need to distinguish whether the optimal value of each constructed $\kMaxIP{(k,h)}$ instance is $\binom k3T$ or $(\binom k3 - 1)T + T/2$. Thus, an additive $\varepsilon d' < T/6$-approximation suffices. Since $T = c \cdot 2^{c_1} \cdot \log n$, setting $\varepsilon < \frac{c 2^{c_1}}{\tau^{\poly(k, c/\gamma)}}$ is enough. By <ref>, we can compute such an additive approximation using $\calA$ in time $\Order((nd')^{k-\delta'})$ for some $\delta' > 0$.

Hence, by constructing $\tilde\Order(n^{1+\gamma})$ instances of $\kMaxIP{(k,h)}$ and computing the additive $\varepsilon d'$-approximation using $\calA$, we can decide the original (k,3) instance in time

\begin{equation*}
\tilde\Order(n^{1+\gamma} + n^{\gamma}(nd' + (nd')^{k-\delta'}))  = \tilde\Order(n^{k + \gamma - \delta'})
\end{equation*}

By choosing $\gamma < \delta'$, this contradicts the Sparse  hypothesis.

§ DISTRIBUTED PCP AND EXTENSIONS

In this section we sketch how <ref> can be obtained by combining previously known results in [36], [60] and [74].

<ref> was shown in <cit.>, but for the case of $k = 2$ and using $\kMaxIP{2}$ as the target problem. Our version is a simple generalization for the case of arbitrary $k$, and to reduce to any $\VMax(\phi)$ with $\Hand(\phi) = k$. The main ingredient to obtain the parameters of the reduction as in <ref>, is an efficient MA protocol[More precisely, the communication model is the Simultaneous Messaging Passing model [82, 21], as referred to in [60]. But we stick to Chen's notation [36].] for Set-Disjointness:

In the $\Disj_{d,k}$ problem there are $k$ players, each of which receives a vector $x_i \in \{0,1\}^d$ as input. Their goal is to jointly decide whether $\langle x_1,\dots,x_k \rangle = 0$.

We say that a communication protocol is $(m, r, \ell, s)$-efficient for a communication problem if the following holds:

* There are $k$ players in the protocol $P_1,\dots,P_k$ and Merlin. Each player $P_i$ holds an input $x_i$.

* The protocol is one-round with public randomness. The following happens sequentially:

* Merlin sends an advice string of length $m$ to $P_1$, which is a function of $x_1,\dots,x_k$.

* The players jointly draw $r$ random bits.

* Each player $P_i$ for $2 \leq i \leq k$ sends an $\ell$-bit message to $P_1$, which is a deterministic function of the input and randomness.

* Upon receiving the messages, $P_1$ decides to accept or reject.

* The protocol has full completeness and soundness $s \in (0,1]$.

* The computation of players is polynomial in their input lengths.

In particular, to obtain <ref> one needs the generalization of the protocol for $\Disj_{m,2}$ by Rubinstein [74] to the case of $k$ players. This generalization was written explicitly in [60], where the authors explicitly acknowledge that Rubinstein suggested them the generalization.

For every $d, k$ and $\alpha > 0$, there exists a $(d/\alpha, \log_2 d, \poly(k,\alpha),1/2)$-efficient protocol for $\Disj_{d, k}$.

Lemma <ref> improves upon the Aaronson and Wigderson protocol [1] used in the original distributed PCP reduction [7], which if extended to $k$ players, has parameters $(dk/\log d,\allowbreak \Order_k(\log d),\allowbreak \Order_k(\log^3 d), 1/2)$. As mentioned earlier, this key technical improvement was introduced by Rubinstein [74] via algebraic geometry codes.

Note that the protocol of <ref> uses $\Order(\log d)$ random bits to obtain soundness $1/2$. To boost the soundness to $\varepsilon$, the standard way is to repeat the protocol (with the same advice) $\Order(\log \varepsilon^{-1})$-many times. The overall number of random bits used would thus be $\Order(\log d \cdot \log \varepsilon^{-1})$. Chen reduced this to $\Order(\log d + \log \varepsilon^{-1})$ in the case of $k = 2$ via expander walk sampling and using the aforementioned protocol for $\Disj_{d,2}$ as a blackbox. His proof extends in a straightforward way to general $k$ using the protocol from <ref>:

For every $d$, $\alpha > 0$ and $0 < \varepsilon < 1/2$, there exists a $(d/\alpha, \log_2 d + \Order(\log \varepsilon^{-1}), \poly(k, \alpha)\cdot \log(\varepsilon^{-1}), \varepsilon)$-efficient protocol for $\Disj_{d, k}$.

In [7] it was shown that given any communication protocol for $\Disj_{d,2}$, one can obtain a gap introducing reduction from $\kOV{2}$ on dimension $d$, to many instances of $\kMaxIP{2}$ with a gap proportional to the soundness of the protocol. The number of instances produced and the dimension of the constructed instances depend on the parameters of the protocol. This can be easily extended to our case, where we instead start from $\kOV{k}$ and reduce to instances of $\VMax(\phi)$ where $\Hand(\phi) = k$:

Let $\phi: \{0,1\}^k \mapsto \{0,1\}$ have $\Hand(\phi) = k$. Given a $(m, r, \ell, s)$-efficient protocol for $\Disj_{d,k}$, there is a reduction from k on sets of size $n$ and dimension $d$ which constructs $2^m$ instances of $\VMax(\phi)$ with dimension $d' = 2^{r + (k-1) \ell}$ and sparsity $m' = O(n d')$, such that the following holds:

Completeness: If we start from a YES instance of k, then one of the
constructed instances of $\VMax(\phi)$ has $\OPT = 2^r$.
Soundness: If we start from a NO instance of k, then for every
constructed instance of $\VMax(\phi)$ it holds that $\OPT \leq s \cdot 2^r$.

The running time of the reduction is $O(2^{r + (k-1) \ell + m} \cdot n \cdot \poly(d))$.

By <ref>, note that $\Hand(\phi) = k$ if and only if $\phi$ has exactly one satisfying assignment, which we denote by $(\alpha_1,\dots,\alpha_k) \in \{0,1\}^k$.

Consider an instance $X_1,\dots,X_k \subseteq \{0,1\}^d$ of $\kOV{k}$. For each advice string $M \subseteq [2^m]$ we construct an instance
$X^M_1,\dots,X^M_k$ of $\VMax(\phi)$ as follows:

For each random string $R \in [2^r]$ and for each $x_1 \in X_1$ we create a vector $x^{M, R}_1 \in \{0,1\}^{2^{(k-1) \ell}}$. We treat a tuple of messages $(B_2,\dots,B_k)$ where $B_i \in \{0,1\}^\ell$ as an index in $[2^{(k-1)\ell}]$, and each entry of $x^{M, R}_1$ is defined as:

\begin{equation*}
x^{M, R}_1[(B_2,\dots,B_k)] :=
\begin{cases}
\alpha_1 & \text{\parbox{8.5cm}{if $P_1$ accepts on input $x_1$, advice $M$ from Merlin, randomness $R$ and messages $B_2, \ldots, B_k$ from players $P_2, \dots, P_k$,}} \\[3.5ex]
1 - \alpha_1 & \text{otherwise.}
\end{cases}
\end{equation*}

Similarly, for each random string $R \in [2^r]$ and for each $x_i \in X_i$ for $2 \leq i \leq k$ we create a vector $x^{M, R}_i \in \{0,1\}^{2^{(k-1) \ell}}$:

\begin{equation*}
x^{M, R}_i[(B_2,\dots, B_k)] :=
\begin{cases}
\alpha_i & \text{\parbox{8.5cm}{if $P_i$ sends message $B_i$ to $P_1$ on input $x_i$, advice~$M$ from Merlin and randomness $R$,}} \\[2ex]
1 - \alpha_i & \text{otherwise.}
\end{cases}
\end{equation*}

The key observation is that there is exactly one position $j = (B_2,\dots,B_k)$ where $x^{M, R}_i[j] = \alpha_i$ for $2 \leq i \leq k$, corresponding to the actual messages $B_2,\dots,B_k$ sent by players $P_2,\dots,P_k$ in the protocol under randomness $R$ and advice $M$. In particular, it follows that if $P_1$ accepts with these messages, this randomness and this advice then $x^{M, R}_1[j] = \alpha_1$. Thus, since $(\alpha_1,\dots,\alpha_k)$ is the unique satisfying assignment of $\phi$, we have that

\begin{equation*}
\Val(x_1^{M, R},\dots,x_k^{M, R}) =
\begin{cases}
1 & \text{\parbox{8.5cm}{if $P_1$ accepts on inputs $x_1, \dots, x_k$, advice~$M$ from Merlin and randomness $R$,}} \\[2ex]
0 & \text{otherwise.}
\end{cases}
\end{equation*}

Finally, each $x_i^M \in X_i^M$ is constructed by concatenating $x_i^{M, R}$ over all random strings $R \in [2^r]$, which means that $X_i^M \subseteq \{0,1\}^{2^{r + (k-1) b}}$. And by the previous argument we have that

\begin{equation*}
\Val(x_1^M, \dots, x_k^M) = 2^r \cdot \Pr_{R}\Bigg[\text{\parbox{8.1cm}{\centering$P_1$ accepts on inputs $x_1, \dots, x_k$, advice $M$ from Merlin and randomness $R$}}\Bigg]
\end{equation*}

We analyze the completeness, soundness and running time of the reduction:

Completeness: If $X_1,\dots,X_k$ is a YES instance of $\kOV{k}$, then there is an advice $M'$ which makes $P_1$ accept with probability one, and thus  $\OPT = 2^r$ for the instance $X^{M'}_1,\dots,X^{M'}_k$.
Soundness: If $X_1,\dots,X_k$ is a NO instance of $\kOV{k}$, by the soundness of the protocol we have that $\OPT \leq s \cdot 2^r$ for all instances $X^M_1,\dots,X^M_k$, $M \in [2^m]$.
Running Time: We iterate over the $2^m$ possible advice strings, the $2^r$ possible random strings and the $2^{(k-1) \ell}$ possible messages that the players send. Then, we simulate the decision of $P_1$ based on each possible combination of advice, randomness and messages which takes $O(\poly(d))$-time per vector (due to the efficiency of the protocol). Since we do this for $O(n)$ vectors, the overall running time is $O(2^{r + (k-1) \ell + m} \cdot n \cdot \poly(d))$.

Finally, we obtain <ref> by using the protocol from <ref> in the gap reduction from <ref>:

Given an instance of $\kOV{k}$ on sets of size $n$ and dimension $c \log n$, we take the
$(d/\alpha, \log_2 d + \Order(\log \varepsilon^{-1}),
\poly(k, \alpha)\cdot \log(\varepsilon^{-1}), \varepsilon)$-efficient protocol for $\Disj_{d,k}$ from <ref>
with parameters $d := c \log n$, $\alpha := c/\gamma$, and $\varepsilon := 1/\tau$. Plugging it into the reduction from <ref> yields the result.