Constant Inapproximability for PPA

Introduction

The consensus halving problem [Simmons and Su, 2003] is a fair division problem defined by $n$ agents, who each have a valuation function over the unit interval $R=$. The goal is to partition $R$ into two sets $R^{+}$ and $R^{-}$ using at most $n$ cuts, such that all agents agree that $R^{+}$ and $R^{-}$ have the same valuation, or in the $\varepsilon$-approximate version, that all agents agree that $R^{+}$ and $R^{-}$ have valuations that differ by at most $\varepsilon$.

The problem is guaranteed to have a solution and this is usually proved by using the Borsuk-Ulam theorem from topology, or its discrete counterpart, Tucker’s lemma [Simmons and Su, 2003]. In fact, very similar versions of this existence result have been proved in the past in different contexts [Hobby and Rice, 1965; Alon and West, 1986; Alon, 1987]. Since the problem is guaranteed to have a solution, it lies in the complexity class TFNP: the class of total NP search problems. In particular, this means that the problem cannot be NP-hard, unless $\textup{{NP}}=\textup{{co-NP}}$ [Megiddo and Papadimitriou, 1991], and instead, one has to use subclasses of TFNP to classify its complexity.

The consensus halving problem has risen to prominence as it has played a crucial role in the development of the complexity class PPA, a subclass of TFNP defined by Papadimitriou . Indeed, in a breakthrough result, Filos-Ratsikas and Goldberg proved that the problem is complete for PPA. This was the first “natural” complete problem for the class and it has been pivotal in proving further such completeness results. For example, PPA-completeness has since been shown for other “natural” problems such as the necklace splitting problem and the discrete ham sandwich problem [Filos-Ratsikas and Goldberg, 2019], two types of the pizza-sharing problem [Deligkas et al., 2020; Schnider, 2021], and finding fair independent sets in cycles and paths [Haviv, 2021]. We refer to these as natural problems since their definition does not involve any kind of circuit, as opposed to “unnatural” problems like Tucker (the problem associated with Tucker’s Lemma), which was already known to be PPA-complete [Aisenberg et al., 2020], but whose definition involves a Boolean circuit.

Consensus halving has been used in a fundamental way to show PPA-completeness for natural problems, because it bridges the gap between natural and unnatural PPA-complete problems. Specifically, the PPA-hardness results for consensus halving [Filos-Ratsikas and Goldberg, 2018, 2019] reduce from Tucker, and explicitly remove the Boolean circuit by encoding each gate as a consensus halving agent. To the best of our knowledge, all subsequent hardness results for natural problems have reduced from consensus halving.

Prior work has shown that, not only is it PPA-complete to find exact consensus halving solutions for piecewise constant valuation functions, but it is also PPA-complete to find approximate solutions. The initial hardness result of Filos-Ratsikas and Goldberg showed that $\varepsilon$-Consensus-Halving is PPA-complete for an exponentially small $\varepsilon$. The same authors later improved this to obtain a PPA-completeness result for $\varepsilon$-Consensus-Halving with $\varepsilon$ being polynomially small [Filos-Ratsikas and Goldberg, 2019].

The hardness of approximation for consensus halving has then directly led to hardness of approximation for the other natural PPA-complete problems, because all of the PPA-hardness reductions for natural problems that have been discovered so far preserve approximate solutions. So, we have that necklace splitting, discrete ham sandwich, pizza-sharing, and finding fair independent sets in cycles and paths are all PPA-complete to approximate for a polynomially small $\varepsilon$.

In this sense, consensus halving plays a crucial role in the hardness of approximation for natural PPA-complete problems, because any improvement in the hardness result for consensus halving directly leads to an improvement in the hardness results for all of the natural problems that are currently known to be PPA-complete.

The key question left open by previous work is whether $\varepsilon$-Consensus-Halving is PPA-hard, and thus PPA-complete, for a constant $\varepsilon$. While there is no such result in prior work, consensus halving is known to be PPAD-hard for a very small constant $\varepsilon$ [Filos-Ratsikas et al., 2018]. This result actually predates all of the PPA-hardness results and arises from a direct reduction to $\varepsilon$-Consensus-Halving from the Gcircuit problem, which is known to be PPAD-complete for constant $\varepsilon$ [Rubinstein, 2018]. Notably, though, the constant is so small that no prior work has actually given a lower bound on its magnitude.

Furthermore, even ignoring the minuscule $\varepsilon$, this result is somewhat unsatisfying, since it seems unlikely that PPAD-hardness is the correct answer for constant approximation, given that $\textup{{PPAD}}\subseteq\textup{{PPA}}$, and PPA appears to capture a strictly larger class of problems. This is doubly so, since finding a polynomially small approximation is known to be PPA-complete, and thus PPA-completeness of finding constant approximations would be the natural, and tight, answer.

$\varepsilon$-Consensus-Halving is PPA-complete for all $\varepsilon<0.2$.

Thus, we show hardness for a constant $\varepsilon$, improving upon the prior state-of-the-art result, which showed hardness for a polynomially small $\varepsilon$. A direct consequence of this theorem is that the hardness results for all natural problems that are known to be PPA-complete are strengthened as well, and we obtain PPA-hardness for each of the problems for a constant $\varepsilon$.

Our result shows hardness for any $\varepsilon<0.2$, which is notably large compared to other constant inapproximability results for total search problems. For example, the current state-of-the-art hardness results for PPAD-complete problems do show hardness for a constant $\varepsilon$ [Rubinstein, 2018], but as mentioned earlier, that constant is so small that no prior work has given a lower bound on its magnitude. Here we give a constant that is substantial relative to the trivial upper bound of $\varepsilon=1$. We obtain similarly large constants for each of the other natural problems that are known to be PPA-complete, as shown in the following table.

The full details of these follow-on hardness results can be found in Section 1.2.

Moreover, our main result continues to hold even if we severely restrict the valuation functions of the agents.

$\varepsilon$-Consensus-Halving is PPA-complete for all $\varepsilon<0.2$, even if all agents have 3-block uniform valuations.

An agent has a 3-block uniform valuation function if the density function of the valuation is non-zero in at most three intervals, and in each such interval it has the same non-zero value.

Finally, by a standard argument [Filos-Ratsikas et al., 2020], it immediately follows that the hardness result holds even if we allow a few more than just $n$ cuts.

$\varepsilon$-Consensus-Halving is PPA-complete for all $\varepsilon<0.2$, even if all agents have 3-block uniform valuations, and even if $n+n^{1-\delta}$ cuts are allowed for some constant $\delta>0$, where $n$ is the number of agents.

In the next section, we present an overview of the proof of Theorem 1.1, including the new insights that allow us to obtain hardness for a constant $\varepsilon$.

1 Overview of the Main Result

To prove our main result, we reduce $2$D-Tucker, which is known to be PPA-complete [Aisenberg et al., 2020], to $\varepsilon$-Consensus-Halving for all $\varepsilon<0.2$. Here we give an overview of the reduction, and the key challenges that needed to be overcome in order to obtain a constant $\varepsilon$.

In our description of the main ideas and challenges, we will make reference to the three existing PPA-hardness reductions for consensus halving.

Work 1 [Filos-Ratsikas and Goldberg, 2018]: which proves hardness for inverse exponential $\varepsilon$.

Work 2 [Filos-Ratsikas and Goldberg, 2019]: which proves hardness for inverse polynomial $\varepsilon$.

Work 3 [Filos-Ratsikas et al., 2020]: which provides a significantly simplified proof of hardness for inverse polynomial $\varepsilon$.

All three existing works ultimately reduce from $2$D-Tucker, but Works 2 and 3 include a preliminary step, where $2$D-Tucker is reduced to its high-dimensional version: $N$D-Tucker. This seems to be necessary in order to obtain hardness for inverse polynomial $\varepsilon$. Indeed, a similar observation can also be made about analogous results in the study of approximate Nash equilibrium computation [Daskalakis et al., 2009; Chen et al., 2009], where a high-dimensional version of the Brouwer problem is used to achieve hardness for inverse polynomial approximation.

We begin with a very high-level overview of the general structure of the reduction which applies to all three existing works, as well as to ours. Informally, an $N$D-Tucker instance is defined over an $N$-dimensional grid $G=[m]\times[m]\times\dots\times[m]$ with side length $m$. The instance gives a labelling function $\lambda:G\rightarrow\{-N,\dots,-1,1,\dots,N\}$, presented as a Boolean circuit, that assigns each point in the grid a label that is either $+i$ or $-i$ for some $i$ in the range $1\leq i\leq N$. Additionally, the labelling satisfies an antipodality condition on the boundary: letting $\overline{x_{i}}:=m_{i}-x_{i}+1$, it holds that $\lambda(\overline{x})=-\lambda(x)$ whenever $x$ lies on the boundary of $G$. The goal is to find two points $x$ and $y$ on the grid, such that $x$ and $y$ are within $L_{\infty}$ distance 1 of each other, and $\lambda(x)=-\lambda(y)$. Such a pair of points is guaranteed to exist by Tucker’s Lemma [Tucker, 1945], and the problem of finding one is PPA-complete even for constant $m$, as shown in Work 2 by reducing from $2$D-Tucker. The problem $2$D-Tucker is defined in the same way, except that $N=2$, and $m$ is required to be exponentially large for the problem to be PPA-complete [Aisenberg et al., 2020].

We are now ready to present the high-level setup used in all three previous works. The specifics of the reductions in Works 1 and 2 are significantly more involved than what is presented here, and so the presentation below should be seen as mostly applying to the simplified proof of Work 3 (while still representing the underlying core structure hidden behind the reductions in Works 1 and 2). The $\varepsilon$-Consensus-Halving instance $\textup{CH}(\lambda)$ is constructed as follows:

The line $R=$ consists of two intervals $I$ and $C$. We think of $I$ as the input region (also called coordinate-encoding region in prior work), and $C$ as the circuit region (also called circuit-encoding region). In any solution $S=(R^{+},R^{-})$ to the instance $\textup{CH}(\lambda)$, $I$ will be partitioned into two regions $I^{+}:=I\cap R^{+}$ and $I^{-}:=I\cap R^{-}$. The exact way in which $I$ is partitioned encodes a point $z:=z(I^{+},I^{-})$ in some domain. In Work 1, this domain is a locally two-dimensional Möbius strip, while in Work 2, it is a high-dimensional generalization of that. Work 3 significantly simplifies this encoding by letting the domain simply be the $N$-dimensional unit hypercube. In all three cases, the grid $G$ of the $N$D-Tucker instance $\lambda$ is embedded in the domain in question, and so the partition $(I^{+},I^{-})$ ultimately encodes a point $x:=x(I^{+},I^{-})\in G$.

To “extract” the point $x\in G$ from $(I^{+},I^{-})$, a binary decoding step is performed where the continuous information that is encoded in $(I^{+},I^{-})$ is converted into bit values that represent $x_{i}$. Mechanically, this is implemented by introducing a set of agents in $\textup{CH}(\lambda)$ who ensure that cuts (between $R^{+}$ and $R^{-}$) are placed in specified regions of $C\subset$ to encode either a bit or a $1$ bit. In Works 1 and 2, this binary decoding is performed “at the source”, namely the information read from $I$ is essentially binary, and then further processed by simulating Boolean gates. In Work $3$, the information read from $I$ is continuous and then further processed by simulating arithmetic gates. The arithmetic gates are then used to perform the bit decoding.

As is common in PPAD and PPA reductions, the Boolean decoding step from $z$ to $x$ can fail for certain values, and if the decoding step fails then nonsensical values will be produced. To address this, instead of just decoding $z$, a large number of points surrounding the encoded point $z$ are decoded, where the samples are chosen to ensure that only a small number of the decoding steps fail. If $K$ samples are taken, then this gives a sequence of points $x^{1},x^{2},\dots,x^{K}$, most of which are valid bit representations of points in $G$, and a small number of which contain nonsensical values. Importantly, the sampling is performed such that all resulting (correctly) decoded points in $G$ lie within $L_{\infty}$ distance $1$ of each other.

The next step is to simulate the execution of the Tucker labelling circuit $\lambda$ on the inputs $x^{1},x^{2},\dots,x^{K}$. For this, $K$ completely independent copies of the circuit $\lambda$ are simulated, each within its own sub-region $C^{1},\dots,C^{K}$ of the circuit region $C$. The region $C^{k}$ is fed input $x^{k}$ and so is used to compute $\lambda(x^{k})$. Mechanically, each gate in each circuit is simulated by a set of agents who ensure that the output of each gate is encoded by a cut in a specified region of $C^{k}$, allowing other agents to read that value to simulate other gates.

The last step is to average the outputs of the circuits. Specifically, for each dimension $i\in[N]$, we introduce an agent that computes the average $L(i)=\frac{1}{K}\sum_{k=1}^{K}y^{k}_{i}$ and enforces that $L(i)$ be $\varepsilon$-close to zero for all $i$. With $K$ being chosen to be suitably large, the effect of the incorrectly decoded points becomes negligible, and so it is only possible for $L(i)$ to be close to zero for all $i$ if, for each dimension $i$, there are a roughly equal number of points with label $+i$ and label $-i$. Since all of the input points lie within $L_{\infty}$ distance $1$ of each other, this implies that we have a solution to the Tucker instance, namely, we can extract from $x^{1},\dots,x^{K}$ two points yielding a solution to $N$D-Tucker. Mechanically, this is implemented by a set of $N$ agents, one for each dimension $i$, enforcing that $L(i)$ is close to zero for a specific label $i$.

The final – and crucial – complication that significantly differentiates these reductions from more standard PPAD-hardness reductions is the presence of stray cuts. Indeed, the construction we have described works perfectly assuming that there are $N$ cuts in the input region $I$. However, nothing forces these $N$ cuts to be made in the input region. If there are less than $N$ cuts in the input region, then we think of the missing cuts as having become stray cuts that can interfere with the rest of the construction, in particular the various circuit simulations. Indeed, a stray cut can essentially destroy the output of one of the circuit simulations by occurring in the corresponding region $C^{k}$. Fortunately, this is easy to fix by taking enough additional samples and copies of the circuit.

The more problematic – and conceptually important – interference caused by stray cuts is that a single stray cut can influence any fraction of the circuits (for example, half of them) by “changing their perception of whether a bit is $1$ or .” Intuitively, any solution $S=(R^{+},R^{-})$ of $\textup{CH}(\lambda)$ remains a solution if we flip $+$ and $-$, i.e., if we let $S^{\prime}=(R^{-},R^{+})$. This symmetry has the following important consequence: in order to perform a logical operation such as AND, which does not commute with bit-flipping (i.e., $\textup{AND}(\lnot b_{1},\lnot b_{2})\neq\lnot\textup{AND}(b_{1},b_{2})$), the circuit needs to be given access to some ground-truth value. This ground-truth essentially helps the circuit differentiate between bits $1$ and , and thus allows it to implement logical gates such as AND. If there are no stray cuts, then it is not too hard to ensure that all the copies of the circuit see the same ground-truth. But a single stray cut can change the ground-truth perception of half the circuits. By a careful construction, it is possible to ensure that if circuit $C^{k}$’s perception of the ground-truth is altered by a stray cut, then it will output $-\lambda(\overline{x^{k}})$ instead of $\lambda(x^{k})$. Furthermore, the construction ensures that if there are less than $N$ cuts in $I$, and thus at least one stray cut, then all the correctly decoded points amongst $x^{1},\dots,x^{K}$ lie on the boundary of $G$. Using the antipodality conditions of $\lambda$, it follows that $-\lambda(\overline{x^{k}})=\lambda(x^{k})$ for all valid points $x^{k}$, and thus the difference in ground-truth between the circuit copies does not matter anymore.

In a certain sense, stray cuts are necessary for any reduction proving PPA-hardness for the problem. For example, if there was some trick to enforce that $N$ cuts lie in $I$ in the reduction above, then the reduction would not have made use of the antipodality condition of $\lambda$. This is not possible, since we could then reduce from a circuit $\lambda$ that has no solution, but $\textup{CH}(\lambda)$ always has a solution. More generally, it can be shown that any reduction where each cut has its own disjoint reserved region (where it must lie) can only prove PPAD-hardness at best. Indeed, in that case those instances can be reduced to the problem of finding a Brouwer fixed point.

Our reduction follows this basic template, but requires overcoming various challenges in order to obtain a constant $\varepsilon$.

While the setup described above is sufficient to obtain hardness for a polynomially small $\varepsilon$, the encoding of the Tucker solutions fails when one considers a constant $\varepsilon$. Specifically, in the computation of $L(i)$, note that most of the terms will be zero, corresponding to points that do not have label $i$. When $K$ is chosen to be polynomially large, as it is in all prior works, then the values of $L(i)$ become polynomially small. This does not cause issues when $\varepsilon$ is also polynomially small, as one can still distinguish $L(i)$ being close to zero, and $L(i)$ being far from zero. But when $\varepsilon$ is a constant we lose that power, and the reduction breaks.

One idea is to try to get away with only a constant number $K$ of samples and circuit copies. Indeed, prior work by Rubinstein in the context of PPAD has succeeded in performing the so-called averaging trick with only a constant number of samples. Unfortunately, there seems to be a fundamental obstacle to this kind of approach here: there are up to $N$ stray cuts that can “destroy” up to $N$ circuit copies, and thus any constant number $K$ of copies will not be enough.

Intuitively, in $N$D-StrongTucker the label $\lambda(x)$ carries much more information than in $N$D-Tucker. Indeed, in a certain sense, the label at some point $x$ now has to pick a direction in each dimension $i\in[N]$, and cannot remain “neutral” in some dimension. This is exactly what our reduction to $\varepsilon$-Consensus-Halving requires.

We show that $N$D-StrongTucker is PPA-complete, even when the side-length of the grid is equal to $8$ in all dimensions. We then use $N$D-StrongTucker in the reduction to $\varepsilon$-Consensus-Halving. This averts the problems mentioned above, since now each sum $L(i)$ consists of summands that are $+1$ and $-1$, and thus $L(i)$ will not be (constantly) close to zero unless both $+1$ and $-1$ appear as labels in dimension $i$.

To show hardness for $N$D-StrongTucker, we reduce from $2$D-Tucker. We first show that $2$D-Tucker reduces to $2$D-StrongTucker by a fairly direct reduction that maps each of the labels $-2,-1,1,2$ from $2$D-Tucker to one of the four possible vector labels in $2$D-StrongTucker. Such a simple mapping is not possible in higher dimensions, however, and so we then use the hardness of $2$D-StrongTucker to show hardness for $N$D-StrongTucker. Here we use a careful adaptation of the snake embedding idea that was used to reduce $2$D-Tucker to $N$D-Tucker in Work 2. This construction allows us to decrease the width of one of the dimensions by a constant fraction, by introducing a new dimension (of small width) and folding the instance within this new dimension (see Figure 1). While this type of embedding has been used in the past, a fresh construction is needed in our case to deal with the fact that all points have $N$ labels in an $N$D-StrongTucker instance.

The PPA-hard instances of $2$D-Tucker have exponential width in both dimensions. Repeatedly applying the snake embedding allows us to reduce this to an instance in which all dimensions have width $8$. As it turns out, in our final reduction to $\varepsilon$-Consensus-Halving, the constant width of the instance is not strictly necessary (an instance with polynomial widths would suffice), but we believe that the hardness for constant width may have applications elsewhere.

With this more powerful Tucker problem in hand, one could hope to obtain hardness for constant $\varepsilon$ by simply replacing $N$D-Tucker by $N$D-StrongTucker in the reduction of Work 3. Unfortunately, there is another point in that reduction that relies on inverse polynomial $\varepsilon$: the sampling. Indeed, that work makes use of arithmetic gates and the so-called equi-angle sampling technique, which has been used in the past to prove PPAD-hardness for the Nash equilibrium problem [Chen et al., 2009]. Unfortunately, this sampling technique cannot be combined with constant-error-arithmetic gates. Since we have to take a polynomial number of samples (recall that the stray cuts force us to do this), and the error in each gate is constant, we will not obtain enough distinct samples to ensure that most of them are correctly decoded.

In order to overcome this obstacle, we switch to using Boolean gates, instead of arithmetic gates, like the two original works (Works 1 and 2), while keeping all the other major simplifications introduced by Work 3. Thinking in terms of Boolean gates allows us to construct a very simple, yet very powerful sampling gadget. We subdivide the input region $I$ into subregions $I_{1},\dots,I_{N}$, one for each dimension. The idea is that the $i$th coordinate of the encoded points will be extracted from $I_{i}$. Next, we subdivide $I_{i}$ into $7N$ subregions $I_{i,1},\dots,I_{i,7N}$. We essentially read one bit from each of those $7N$ subregions and interpret the resulting bitstring as the unary representation of a number in $[7N]$. Then, this number is scaled down to lie in $$, in order to correspond to a coordinate in$G=^{N}$. The crucial point is that we read the coordinate in unary representation and with more precision than actually needed. Thus, even if$N$bits fail, the final number in$$will move by at most$1$.

With this simplified sampling technique in hand, it is now possible to reduce to $\varepsilon$-Consensus-Halving for some constant $\varepsilon>0$.

Our final challenge is to push the reduction technique introduced in Works 1 and 2, and simplified in Work 3, to its limits, by trying to obtain hardness for the largest possible value of $\varepsilon$. This effort results in a streamlined reduction that still follows the high-level structure presented above, but where each individual component is as lightweight as possible. Some note-worthy points are:

Switching to Boolean gates, which was very useful to overcome the previous challenge, now becomes a necessity when one is interested in obtaining large constant values of $\varepsilon$. In particular, with the new sampling approach introduced above, the width of $N$D-StrongTucker does not limit how much we can increase $\varepsilon$. In other words, improving the PPA-hardness of $N$D-StrongTucker to grids of width less than $8$ would not yield an improvement to the $\varepsilon$ we obtain.

Our reduction ends up only using two types of gates: NOT and NAND. Each of these two gates can be implemented by a single agent. The use of NAND instead of AND is not significant, but just for convenience (AND would require creating a NAND gate and then using a NOT gate on its output).

The natural construction of the NAND gate requires $\varepsilon<1/7$. In order to improve this to $\varepsilon<1/5$, we eliminate one of the key components introduced in Work 3, the so-called constant creation region, and replace it by an ad-hoc argument which involves arguing about the parity of the number of cuts. This kind of argument is more reminiscent of Works 1 and 2.

Putting all these optimizations together, we obtain the reduction presented in Section 4, which proves PPA-hardness of $\varepsilon$-Consensus-Halving for any constant $\varepsilon<1/5$. The construction also provides a satisfying explanation for why we cannot go above $1/5$ with current techniques. Indeed, it turns out that for NOT gates $\varepsilon<1/3$ would suffice, but it is the NAND gates which require $\varepsilon<1/5$. Other parts of the reduction would also work with $\varepsilon<1/3$. Thus, the NAND gates are clearly identified as the bottleneck for improving $\varepsilon$. More generally, it can be seen that any gate that combines two bits into one in some non-trivial way (e.g., not just copying the first input bit), will require $\varepsilon<1/5$. Nevertheless, this limitation could be lifted if the reduction was able to handle more than $N$ stray cuts. None of the existing works provide a way to handle this, since all of them crucially rely on there being at most $N$ stray cuts. Indeed, if there are $N+1$ stray cuts, then we can no longer argue that if a stray cut affects our circuits, then we are on the boundary of $G$.

2 Direct Consequences

Our hardness result for $\varepsilon$-Consensus-Halving directly yields improved hardness results for every natural problem that is currently known to be PPA-complete. In this section we give the details for these improved hardness results.

In NecklaceSplitting, we are given a necklace with beads of $n$ colours, and we want to split the necklace into two (in general, non-contiguous) parts by making at most $n$ cuts, such that both parts contain half of the beads of each colour. It was shown by Goldberg and West and Alon and West that the problem always admits a solution, and later Alon extended this result to the variant where the necklace must be divided into $k$ parts rather than two.

PPA-completeness for the problem was proven by Filos-Ratsikas and Goldberg via a reduction from $\varepsilon$-Consensus-Halving for an inversely-polynomial $\varepsilon$. In addition, in [Filos-Ratsikas and Goldberg, 2018] it was proven that the approximate version of the problem is PPAD-hard for some small constant $\varepsilon$.

In the approximate version of the problem, denoted as $\varepsilon$-NecklaceSplitting with $\varepsilon\in(0,1)$, the goal is to cut the necklace into two parts such that, for each colour, the discrepancy between the two parts is bounded by $\varepsilon$. Formally, if there are $B_{i}$ beads of colour $i$ and $B_{i}^{+},B_{i}^{-}$ correspond to the number of beads of colour $i$ in each of the two parts, in an $\varepsilon$-solution it holds that $|B_{i}^{+}-B_{i}^{-}|\leq\varepsilon\cdot B_{i}$. The reduction presented in [Filos-Ratsikas and Goldberg, 2018] increases the error of the $\varepsilon$-Consensus-Halving instance by only a polynomially small amountWe note that [Filos-Ratsikas and Goldberg, 2018] appear to have mistakenly defined $\varepsilon$-NecklaceSplitting with $\varepsilon$ denoting the discrepancy between the number of beads in each of the two parts, rather than normalising $\varepsilon$ so that it is expressed relative to the total number of beads. However, their proof and result actually apply to the definition that we give here., so by applying our our main result, we obtain the following.

$\varepsilon$-NecklaceSplitting is PPA-complete for every constant $\varepsilon<0.2$, even if $n+n^{1-\delta}$ cuts are allowed for some constant $\delta>0$.

In DiscreteHamSandwich, as defined by Papadimitriou , we are given $n$ sets of points with integer coordinates in $d$ dimensional space, where $d\geq n$. The task is to find a hyperplane that cuts the space into two halfspaces, such that each halfspace contains half of the points of each set. If any points lie on the plane, then we are allowed to place each of them on either side. [Filos-Ratsikas and Goldberg, 2019] proved that the problem is PPA-complete, via a reduction from NecklaceSplitting.

In the approximate version of the problem, denoted $\varepsilon$-DiscreteHamSandwich, we want to find a hyperplane such that, for every set, the discrepancy between the number of points contained in the two halfspaces is bounded by $\varepsilon$. Formally, if there are $S_{i}$ points for set $i$ and $S_{i}^{+},S_{i}^{-}$ correspond to the number of points belonging to the two halfspaces, in an $\varepsilon$-solution we must have $|S_{i}^{+}-S_{i}^{-}|\leq\varepsilon\cdot S_{i}$. The reduction between DiscreteHamSandwich and NecklaceSplitting presented by Filos-Ratsikas and Goldberg is approximation preserving, so we get the following theorem.

$\varepsilon$-DiscreteHamSandwich is PPA-complete for every constant $\varepsilon<0.2$, even if $d=n+n^{1-\delta}$ for some constant $\delta>0$.

In pizza sharing problems we are given measurable objects that are embedded in the two-dimensional plane, and we are asked to make a number of cuts in order to divide each mass into two equally sized portions. Two versions of this problem have been studied in the literature.

In the SquarePizzaSharing problem, there are $n$ masses in the plane, and the task is to simultaneously bisect all masses via a square-cut: a path that is the union of horizontal and vertical line segments. In [Karasev et al., 2016] it was proven that a path with $n-1$ turns can always bisect all $n$ masses.

Both problems were proven to be PPA-complete when $\varepsilon$ is inversely polynomial and PPAD-hard for a small constant $\varepsilon\in(0,1)$ via direct reductions from Consensus-Halving [Deligkas et al., 2020; Schnider, 2021]. Using the reductions from [Deligkas et al., 2020], which increase the error by at most a polynomially small amount, alongside our main theorem yields the following.

$\varepsilon$-StraightPizzaSharing is PPA-complete for every constant $\varepsilon<0.2$, even if $n+n^{1-\delta}$ cuts are allowed for some constant $\delta>0$.

$\varepsilon$-SquarePizzaSharing is PPA-complete for every constant $\varepsilon<0.2$, even if the square-cut path is allowed to have $n+n^{1-\delta}$ turns for some constant $\delta>0$.

In this setting, we are given a graph $G$ whose vertices are partitioned into $n$ sets $V_{1},\ldots,V_{n}$. The task is to find two independent sets of $G$ such that every $V_{i}$ is covered in a “fair” manner. In particular, we are interested in the setting where $G$ is a cycle or a path, since it was proven that such graphs possess fair independent sets [Aharoni et al., 2017; Alishahi and Meunier, 2017; Black et al., 2020].

More specifically, Alishahi and Meunier proved that if $G$ is a cycle of $m$ vertices and $n$ has the same parity as $m$, then there exist two disjoint independent sets $S_{1}$ and $S_{2}$, such that for every $\varepsilon\in[0,\frac{1}{2}]$ and every $i\in[n]$ it holds that $|V_{i}\cap(S_{1}\cup S_{2})|=|V_{i}|-1$ and $|S_{j}\cap V_{i}|\geq(\frac{1}{2}-\varepsilon)\cdot|V_{i}|-1$ for all $j\in\{1,2\}$. We use $\varepsilon$-FairSplitCycle to denote the problem of finding two such independent sets.

A similar theorem was shown for paths by Black et al. : if $G$ is a path and every set $V_{i}$ contains an odd number of points, then there exist two independent sets $S_{1}$ and $S_{2}$, covering all but at most $n$ vertices of $G$ such that for every $\varepsilon\in[0,\frac{1}{2}]$ and every $i\in[n]$ it holds that |S_{1}\cap V_{i}|\in\big{[}(\frac{1}{2}-\varepsilon)\cdot|V_{i}|-1,(\frac{1}{2}+\varepsilon)\cdot|V_{i}|\big{]}. We use $\varepsilon$-FairSplitPath to denote the corresponding computational problem.

Hardness was shown for both problems by Haviv , who proved that both problems are PPA-complete for a polynomially small $\varepsilon$ and that they are PPAD-hard for a small constant $\varepsilon$. The hardness is shown by a reduction from $\varepsilon$-Consensus-Halving to $\frac{\varepsilon}{4}$-FairSplitPath and then a follow-on reduction from $\varepsilon$-FairSplitPath to $\varepsilon$-FairSplitCycle. Combining these reductions with our main theorem yields the following.

$\varepsilon$-FairSplitPath and $\varepsilon$-FairSplitCycle are PPA-complete for every constant $\varepsilon<0.05$.

3 Further related work

There are various other works that relate to ours, some of which dealt with PPA-hardness and some of which studied the consensus halving problem.

In a recent work by Deligkas et al. [2021b] the main question was “How does the complexity of consensus halving depend on the number of agents?”. This paper’s main result is a dichotomy between 2 and 3 agents when the valuations are monotone (but possibly non-additive). In particular, for the former case the problem is polynomial time solvable, while for the latter it is PPA-complete. If the monotonicity property is dropped, then both cases become PPA-complete. Furthermore, for the case of a single agent (and even for $n$ agents with identical valuations) the problem is polynomial time solvable.

Alon and Graur present a set of strong positive results on the $\varepsilon$-NecklaceSplitting problem. They present efficient algorithms for a relaxed version of this problem where more than $n$ cuts are allowed. In particular, for an instance whose beads can take $n$ colours, and can be at most $m$ per colour, they give an offline and an online algorithm that is efficient and deterministic, which provide a solution by making at most $O(n(\log m+O(1)))$ and $O(m^{2/3}\cdot n(\log n)^{1/3})$ cuts, respectively, for $\varepsilon=0$. For $\varepsilon>0$, the same algorithms work with the aforementioned running time, by substituting $m$ with $1/\varepsilon$. These algorithms also work for the $\varepsilon$-Consensus-Halving problem when we are allowed to use more than $n$ cuts. Their positive results extend to the generalization of NecklaceSplitting in which, instead of wishing to split each colour’s beads into two parts, we split them into $k\geq 2$ parts [Alon, 1987]. For detailed definitions of this and related problems, as well as their related complexity classes, see [Filos-Ratsikas et al., 2021], and [Hollender, 2021].

In [Goldberg et al., 2020] the problem under study deviates slightly from the typical consensus halving problem. There are (divisible) items and they are not presented in a linear order, but rather unordered, with agents having linear and additively separable utilities over them. In this work the authors provide polynomial time algorithms even for the more general Consensus-Halving problem where we do not split the probability measures in two, but in $k\geq 2$ parts, and show that for a slightly non-linear valuation class the problem becomes PPAD-hard. For the case where the items are in a specific order, they show that the problem is PPA-complete.

Preliminaries

An instance of $\varepsilon$-Consensus-Halving consists of $n$ agents with piecewise constant valuation functions over the interval $R=$. A solution is a partition of the interval $R$ into two regions $R^{+}$ and $R^{-}$, using at most $n$ cuts, where every agent agrees that the value of $R^{+}$ is at most $\varepsilon$-away from the value for $R^{-}$. Formally, in a solution of $\varepsilon$-Consensus-Halving it holds that $|v_{i}(R^{+})-v_{i}(R^{-})|\leq\varepsilon$ for every $i\in[n]$.

In this paper we will show a hardness result for $\varepsilon$-Consensus-Halving by reducing from the $2$D-Tucker problem.

An instance of $2$D-Tucker consists of a labelling function $\lambda:[m]\times[m]\to\{\pm 1,\pm 2\}$ such that for $1\leq i,j\leq m$, $\lambda(i,1)=-\lambda(m-i+1,m)$ and $\lambda(1,j)=-\lambda(m,m-j+1)$. A solution to such an instance is a pair of vertices $(x_{1},y_{1})$, $(x_{2},y_{2})$ with $|x_{1}-x_{2}|\leq 1$ and $|y_{1}-y_{2}|\leq 1$ such that $\lambda(x_{1},y_{1})=-\lambda(x_{2},y_{2})$.

The labelling $\lambda$ is given as a Boolean circuit. $2$D-Tucker is known to be PPA-complete; Papadimitriou proved membership in PPA and Aisenberg et al. proved PPA-hardness.

Other versions of Tucker’s lemma have also been shown to be PPA-complete [Deng et al., 2017; Filos-Ratsikas and Goldberg, 2019].

Hardness of StrongTucker

In this section we introduce a new problem, $N$D-StrongTucker, and we show that it is PPA-hard for any $N\geq 2$. Our reduction from $N$D-StrongTucker to $\varepsilon$-Consensus-Halving in Section 4 will also show that the problem is in PPA, and hence the problem is PPA-complete.

We begin by introducing some notation. Consider points $\mathbf{z}_{1},\dots,\mathbf{z}_{r}$ and a labelling $\lambda$, such that for any $j\in[r]$ we have $\lambda(\mathbf{z}_{j})\in\{-1,+1\}^{N}$. We say that $\mathbf{z}_{1},\dots,\mathbf{z}_{r}$ cover all labels if for all $i\in[N]$ and $v\in\{-1,+1\}$ there exists a $j\in[r]$ with $[\lambda(\mathbf{z}_{j})]_{i}=v$. Consider an $N$-dimensional grid $[m_{1}]\times\dots\times[m_{N}]$ of points and a labelling $\lambda:[m_{1}]\times\dots\times[m_{N}]\to L$ for some co-domain $L$. The antipodal point of a point $\mathbf{x}=(x_{1},\dots,x_{N})$ that lies on the boundary of the grid (i.e., $x_{i}=1$ or $x_{i}=m_{i}$ for some $i$) is the point $\overline{\mathbf{x}}:=(m_{1}-x_{1}+1,\dots,m_{N}-x_{N}+1)$. We say that the labelling satisfies antipodality if $\lambda(\overline{\mathbf{x}})=-\lambda(\mathbf{x})$ for every $\mathbf{x}$ on the boundary.

We now define an auxiliary lemma that will be useful in this and the following section.

Consider $r\geq N+1$ points $\mathbf{z}_{1},\dots,\mathbf{z}_{r}$ and a labelling $\lambda$, such that for any $j\in[r]$ we have $\lambda(\mathbf{z}_{j})\in\{-1,+1\}^{N}$. If these points cover all labels then there exists an $N$-subset of the aforementioned points that covers all labels. Furthermore, we can recover these $N$ points in polynomial time.

Consider the set $T:=\{\mathbf{z}_{1},\dots,\mathbf{z}_{r}\}$. We will first show that there exists a $(N+1)$-subset of $T$, namely, $\mathbf{z}^{*}_{1},\dots,\mathbf{z}^{*}_{N+1}$, that covers all labels. Consider an arbitrary point to serve as our desired $\mathbf{z}^{*}_{1}$, without loss of generality $\mathbf{z}_{1}$, with its label $\lambda(\mathbf{z}_{1})$. Then, find a point $\mathbf{z}^{*}_{2}\in T$ such that $[\lambda(\mathbf{z}^{*}_{2})]_{1}=-[\lambda(\mathbf{z}_{1})]_{1}$. Next, find another point $\mathbf{z}^{*}_{3}\in T$ such that $[\lambda(\mathbf{z}^{*}_{3})]_{2}=-[\lambda(\mathbf{z}_{1})]_{2}$. Similarly, for $j\in\{4,5,\dots,N+1\}$ find points $\mathbf{z}^{*}_{j}\in T$ such that $[\lambda(\mathbf{z}^{*}_{j})]_{j-1}=-[\lambda(\mathbf{z}_{1})]_{j-1}$. The set $\{\mathbf{z}^{*}_{1},\dots,\mathbf{z}^{*}_{N+1}\}$ that we found has cardinality at most $N+1$, and covers all labels.

Now consider the set $S:=\{\mathbf{z}^{*}_{1},\dots,\mathbf{z}^{*}_{N+1}\}$. For the sake of contradiction, assume there is no $N$-subset of $S$ that satisfies the claim of the lemma. Let us create all $N$-subsets of $S$ as follows:

Now consider the function $f:\{S_{1},\dots,S_{N+1}\}\to[N]$ defined as:

Note that $f$ is well-defined since, by assumption, every $S_{j}$ has such a minimum index. Then, by the pigeonhole principle, this function maps two elements $S_{j^{\prime}},S_{j^{\prime\prime}}$ of its domain to the same value $i^{\prime}\in[N]$, i.e. $f(S_{j^{\prime}})=f(S_{j^{\prime\prime}})=i^{\prime}$. Therefore, the set of points $S_{j^{\prime}}\cup S_{j^{\prime\prime}}$ also has the property that the $i^{\prime}$-th coordinate of all its points’ labels has the same value in $\{-1,+1\}$. But by definition of $S_{j}$’s, we have $S_{j^{\prime}}\cup S_{j^{\prime\prime}}=S$, thus our initial assumption that the points of $S$ cover all labels does not hold (the label-coordinate $i^{\prime}$ is not covered), which is a contradiction.

To find the set $S$ we need to check $r$ many points in the worst case. To recover from $S$ the required $N$-subset we need to check at most all of its $N+1$ many $N$-subsets. Considering the polynomial time that the labelling circuit $\lambda$ needs in order to provide us with the requested labels of the points in the above procedure, we conclude that the overall time to recover the desired $N$ points is polynomial. ∎

We now formally define $N$D-StrongTucker.

An instance of $N$D-StrongTucker consists of a labelling $\lambda:[m_{1}]\times\dots\times[m_{N}]\to\{-1,+1\}^{N}$ (represented by a Boolean circuit) that satisfies antipodality. A solution consists of $N$ points $\mathbf{z}_{1},\dots,\mathbf{z}_{N}$ that cover all labels, and such that $||\mathbf{z}_{j}-\mathbf{z}_{k}||_{\infty}\leq 1$ for all $j,k\in[N]$.

The following theorem states that $N$D-StrongTucker always has a solution.

Let us have an $N$-dimensional grid $[m_{1}]\times\dots\times[m_{N}]$ of points and a labelling $\lambda:[m_{1}]\times\dots\times[m_{N}]\to\{-1,+1\}^{N}$ that satisfies antipodality. Then, there exist $N$ points $\mathbf{z}_{1},\dots,\mathbf{z}_{N}$ that cover all labels such that $||\mathbf{z}_{j}-\mathbf{z}_{k}||_{\infty}\leq 1$ for all $j,k\in[N]$.

The proof of existence is indirect, and comes from the proof of PPA-inclusion of $N$D-StrongTucker presented in Section 4. In the aforementioned section we prove that $N$D-StrongTucker reduces to $\varepsilon$-Consensus-Halving for any constant $\varepsilon<1/5$. And by the fact that $\varepsilon$-Consensus-Halving is in PPA [Filos-Ratsikas and Goldberg, 2018], we get the required inclusion. Alternatively, one could also reduce the problem to some version of Borsuk-Ulam by taking an appropriate continuous interpolation of the labelling. ∎

2 The reduction

We show PPA-hardness for $N$D-StrongTucker in two steps. We first show that the 2D version of the problem is hard, and then we show that hardness for the 2D case implies hardness for higher dimensional instances. The following theorem shows hardness for $2$D-StrongTucker via a direct reduction from $2$D-Tucker.

$2$D-Tucker is known to be PPA-complete [Aisenberg et al., 2020]. We will reduce this problem to $2$D-StrongTucker straightforwardly by just translating the labelling $\lambda_{T}:[m]\times[m]\to\{\pm 1,\pm 2\}$ of the former to the labelling $\lambda_{ST}:[m]\times[m]\to\{-1,+1\}^{2}$ of the latter as follows. For any point $\mathbf{x}$, if $\lambda_{T}(\mathbf{x})=+2$ then $\lambda_{ST}(\mathbf{x})=(+1,+1)$, if $\lambda_{T}(\mathbf{x})=-2$ then $\lambda_{ST}(\mathbf{x})=(-1,-1)$, if $\lambda_{T}(\mathbf{x})=+1$ then $\lambda_{ST}(\mathbf{x})=(+1,-1)$, and if $\lambda_{T}(\mathbf{x})=-1$ then $\lambda_{ST}(\mathbf{x})=(-1,+1)$. By definition of the problems, it is immediate that their sets of solutions are identical.

By reversing the above translation of the labelling, i.e. turning $\lambda_{ST}$ to $\lambda_{T}$ using the same mapping, we get a reduction from $2$D-StrongTucker to $2$D-Tucker, and hence, the former problem’s membership to PPA. ∎

We will reduce $2$D-StrongTucker with width $m=2^{M}$ to $N$D-StrongTucker with width 8 for some appropriate value of $N=O(M)$. The reduction is, in essence, a careful application of the well-known snake embedding technique [Chen et al., 2009; Filos-Ratsikas and Goldberg, 2019] which was used to reduce $2$D-Tucker to a Tucker problem of higher dimension. We have to carefully apply the latter technique for our problem since we need to make sure that no artificial solutions are introduced in the “folding” process, and that the folded $k$-dimensional instance in each step is a proper $(k+1)$-dimensional instance, meaning that it preserves antipodality. As a final step, we ensure that all dimensions have width exactly $8$.

The snake embedding technique starts from the $2^{M}\times 2^{M}$ $2$D-StrongTucker instance and at each step performs a “folding” on some dimension, decreasing its width to roughly $1/3$ of its size, while creating a new dimension of width $8$. In this way, in roughly $2\cdot\log_{3}2^{M}$ foldings we have created an equal amount of extra dimensions of width at most $8$. In general, given a $k$D-StrongTucker instance for $k\geq 2$, by performing a folding on its $i$-th dimension, we create a $(k+1)$D-StrongTucker instance with new width $m_{i}^{\prime}\leq\left\lceil\frac{m_{i}}{3}\right\rceil+4$ and an extra $(k+1)$-st dimension of width $8$. Finally, we perform two extra foldings to ensure that our initial dimensions $1$ and $2$ have also width $8$.

We now describe a general step of the snake embedding, that is, a step where we are given a $k$D-StrongTucker instance and we fold it into a $(k+1)$D-StrongTucker instance. Pick a dimension of $k$D-StrongTucker, without loss of generality $i\in[k]$, that has maximum width $m_{i}>8$, if any. We will call this the folding dimension, and for some $d\in[m_{i}]$, let us call $d$-th ray the set of points of the grid that have coordinate $d$ in that dimension. According to our folding procedure, the $i$-th dimension will have to be of width of the form $3\cdot s+1$, for some natural $s$. Therefore, for width $m_{i}$ that is not of the aforementioned size, we have to add extra copies of rays in order to bring it to the required width. When we refer to adding copies of rays we mean that we copy sets of points together with their labels. In order to preserve antipodality we have to take care of how many copies of the $1$-st and $m_{i}$-th ray we will add. To achieve this, instead of adding one ray when needed, we can attach four extra rays, namely, two left of coordinate $1$ and two right of coordinate $m_{i}$. Let us call the initial $k$D-StrongTucker instance $I_{ST}$ and the one with proper width $I_{WST}$.

Let us use the following set of rules that depend on the size of $m_{i}$ and preserve antipodality:

If $m_{i}=3\cdot s^{\prime}+2$ we add one copy of the $1$-st ray left of the $1$-st ray and one copy of the $m_{i}$-th ray right of the $m_{i}$-th ray.

If $m_{i}=3\cdot s^{\prime}+1$ we do not need to add any ray.

If $m_{i}=3\cdot s^{\prime}$ we add two copies of the $1$-st ray left of the $1$-st ray and two copies of the $m_{i}$-th ray right of the $m_{i}$-th ray.

In essence, we create two identical (up to the turning points) copies of $I_{WST}$ that we glue together and fold in a snake-like shape. Let us call bottom snake the bottom layer of $I_{WST}$ as appears in Figure 1 (blue/shaded-circle layer), and top snake the top layer of $I_{WST}$ (red/hollow-circle layer). Then we need to take care of the turns of $I_{WST}$ so that they do not introduce artificial solutions. To achieve this, it suffices that the bottom snake is formed by copying the $(s+1)$-st and $(s+2)$-nd rays two times, and the top snake is formed by copying the $2s$-th and $(2s+1)$-st rays two times. Then, the folding in the $i$-th dimension of the bottom and top snakes is as demonstrated in Figure 1.

Next, we add extra rays below the bottom snake and above the top snake (green/shaded-squares and green/hollow respectively in Figure 1). In particular, we add rays whose coordinates in the $i$-th and $(k+1)$-st dimensions are

$(j,1)$ for all $j\in\{1,\dots,s+2\}$ and $(s+3,m)$ for all $m\in\{1,\dots,5\}$, which consist the bottom cap, and symmetrically,

$(j,8)$ for all $j\in\{2,\dots,s+3\}$ and $(1,m)$ for all $m\in\{4,\dots,8\}$, which consist the top cap.

Let us call $I^{*}_{ST}$ the resulting $(k+1)$D-StrongTucker instance. From the described folding procedure, we conclude that by folding the $i$-th dimension of $I_{WST}$ for which $m_{i}=3\cdot s+1$, we generate $I^{*}_{ST}$ which has an extra $(k+1)$-st dimension of width $8$ and its $i$-th dimension has now width $m^{\prime}_{i}=s+3$ (see Figure 1).

From the construction so far, we can determine a surjection of points of the bottom and top snakes in $I^{*}_{ST}$ to points in $I_{WST}$. We only need such a surjection because, as we will show later, no point of the bottom or top cap can participate in a solution of $I^{*}_{ST}$. We will map the ray $(j,m)$ corresponding to the coordinates of the $i$-th and the $(k+1)$-st dimensions of $I^{*}_{ST}$ to the $t$-th ray corresponding to the coordinate of the $i$-th dimension of $I_{WST}$. When we say that we map ray $r_{1}$ to ray $r_{2}$ we imply that any point in $r_{1}$ with fixed coordinates in the $k-1$ of its dimensions maps to the point of $r_{2}$ with the same coordinates of these $k-1$ dimensions. The surjection is as follows.

$(j,m)$ for $j\in\{1,\dots,s+1\}$ and $m\in\{2,3\}$ maps to $t=j$.

$(s+2,m)$ for $m\in\{2,3\}$ maps to $t=s+1$.

$(s+2,m)$ for $m\in\{4,5\}$ maps to $t=s+2$.

$(j,m)$ for $j\in\{3,\dots,s+1\}$ and $m\in\{4,5\}$ maps to $t=2s+3-j$.

$(2,m)$ for $m\in\{4,5\}$ maps to $t=2s$.

$(2,m)$ for $m\in\{6,7\}$ maps to $t=2s+1$.

$(j,m)$ for $j\in\{3,\dots,s+3\}$ and $m\in\{6,7\}$ maps to $t=2s-2+j$.

Having specified the structure of the $(k+1)$D-StrongTucker instance, we have to determine the labels of its points. By the construction described in the previous paragraph, the added rays determine the first $k$ label-coordinates of the points in the bottom and top snakes. The $(k+1)$-st label-coordinate of each point in the two snakes is determined as follows: for the bottom snake its value is $+1$ and for the top snake its value is $-1$. Finally, for all points of the bottom cap the label is $\mathbf{+1}$, i.e., all label-coordinates get value $+1$, and similarly, for all points of the top cap the label is $\mathbf{-1}$.

So far we have made sure that at each step of the folding procedure the $k$-dimensional instance $I_{ST}$ at hand and also its modified version $I_{WST}$ will be proper $k$D-StrongTucker instances. Now we will prove correctness of the reduction by showing that every solution of the final $N$D-StrongTucker instance corresponds to a solution in the initial $2$D-StrongTucker instance. We will show this by proving that at every step $k\geq 2$ of the folding procedure, every solution of the $(k+1)$D-StrongTucker instance $I^{*}_{ST}$ corresponds to a solution of the $k$D-StrongTucker instance $I_{WST}$.

Suppose that $S^{\prime}=\{\mathbf{z}^{\prime}_{1},\dots,\mathbf{z}^{\prime}_{k+1}\}$ is a solution to $I^{*}_{ST}$. Let us prove the following claim.

No point of $S^{\prime}$ belongs to the bottom or top cap.

Similarly, if one of the points from $S^{\prime}$ belonged to the top cap, then the labels of all points in $S^{\prime}$ would have their $(k+1)$-st coordinate equal to $-1$, a contradiction. ∎

By the labelling in the folding we have specified earlier, any solution $S^{\prime}$ has to include at least one point of the bottom snake and at least one point of the top snake, otherwise their $(k+1)$-st label-coordinates would be the same - either $+1$ or $-1$ - contradicting the property of covering all labels. Let us call a point $\mathbf{z}^{\prime}$ of $I^{*}_{ST}$ a bottom corner point if it belongs to one of the copied rays of the bottom snake. Similarly, let us call it a top corner point if it belongs to one of the copied rays in the top snake.

Consider for each $\mathbf{z}^{\prime}_{j}\in S^{\prime}$ the point $\mathbf{z}^{*}_{j}$ of $I_{WST}$ to which it is mapped according to the respective paragraph above. Let $S^{*}=\{\mathbf{z}^{*}_{1},\dots,\mathbf{z}^{*}_{k+1}\}$ be the set of the corresponding $k$-dimensional points of $I_{WST}$.

We are now ready to prove the main theorem of this section.

$N$D-StrongTucker is PPA-complete even when $m_{i}=8$ for all $i\in[N]$.

Therefore, we can ensure that the left-hand side is at most $8$ by forcing the right-hand side to be at most $8$, which can be achieved with $t^{*}=\left\lceil\log_{3}(2\cdot m^{0}_{i}-15)\right\rceil$. Before the first folding (i.e. after making the width proper for folding), the width of dimension $i\in\{1,2\}$ of our initial $2$D-StrongTucker instance will be $m^{0}_{i}\leq 2^{M}+4$, therefore after at most $t^{*}=\left\lceil\log_{3}(2^{M+1}-7)\right\rceil$ foldings we have $m^{t^{*}}_{i}\leq 8$.

Finally, inclusion of $N$D-StrongTucker in PPA comes from the reduction of $N$D-StrongTucker to $\varepsilon$-Consensus-Halving for any constant $\varepsilon<1/5$ presented in Section 4. As shown by Filos-Ratsikas and Goldberg , $\varepsilon$-Consensus-Halving is in PPA, which implies the required inclusion. ∎

Main Reduction

In this section, we prove our main result, Theorem 1.1. Namely, for any constant $\varepsilon<1/5$, we present a polynomial-time reduction from $N$D-StrongTucker to $\varepsilon$-Consensus-Halving. In Section 4.4 we explain how our reduction can be modified to work with 3-block uniform valuations, and thus to also prove Theorem 1.2.

Fix any $\varepsilon\in[0,1/5)$. Let $\lambda$ be an instance of $N$D-StrongTucker, i.e., $\lambda:^{N}\to\{-1,+1\}^{N}$ is provided as a Boolean circuit. We use $\textup{size}(\lambda)$ to denote the representation size of the Boolean circuit $\lambda$. Note that, in particular, $\textup{size}(\lambda)\geq N$. We show how to construct an instance $\textup{CH}_{\varepsilon}(\lambda)$ of $\varepsilon$-Consensus-Halving in time polynomial in $\textup{size}(\lambda)$, such that from any solution of $\textup{CH}_{\varepsilon}(\lambda)$ we can extract in polynomial time a solution to $\lambda$.

The first step of the reduction is to construct a slightly modified version of $\lambda$, that will be more convenient to work with. First of all, we will not think of bits as lying in $\{0,1\}$, but, instead, in $\{-1,+1\}$. Here, $-1$ will represent bit (“False”), and $+1$ will represent bit $1$ (“True”).

With this interpretation in mind, the modified circuit, which we denote by $\widehat{\lambda}$, is defined as follows. The input to $\widehat{\lambda}$ consists of $7N^{2}$ bits, that we think of as a matrix $x\in\{-1,+1\}^{N\times 7N}$. We use $x_{i,j}\in\{-1,+1\}$ to denote the $(i,j)$ entry, and $x_{i}\in\{-1,+1\}^{7N}$ to denote the $i$th row. The circuit outputs $N$ bits representing a label $\{-1,+1\}^{N}$. On input $x$, the circuit performs the following computations.

Compute and output $\lambda(\phi(x))\in\{-1,+1\}^{N}$.

In time polynomial in $\textup{size}(\lambda)$ we construct a Boolean circuit $\widehat{\lambda}$ that performs these computations, and only uses NOT gates and NAND gates. Note that other logical gates can easily be simulated using these two gates.

Intuitively, the circuit $\widehat{\lambda}$ does the following. For any $i\in[N]$, $x_{i}\in\{-1,+1\}^{7N}$ is interpreted as representing a number between $1$ and $8$ with precision roughly $1/N$ (in unary representation). That number is then rounded to obtain an integer $\phi_{i}(x)\in$. Why do we use more bits than needed to represent a number in $$? The reason is that this representation is robust to flipping a few bits. Indeed, it is easy to check that flipping up to$N$bits of$x_{i}\in\{-1,+1\}^{7N}$changes the value of$\phi_{i}(x)$by at most$1$. As a result, we obtain the following:

If $x,x^{\prime}\in\{-1,+1\}^{N\times 7N}$ are such that for all $i\in[N]$, $x_{i}$ and $x_{i}^{\prime}$ differ in at most $N$ bits, then $\|\phi(x)-\phi(x^{\prime})\|_{\infty}\leq 1$.