Consensus-Halving: Does It Ever Get Easier?

Introduction

The topic of fair division has been in the focus of research in economics and mathematics, since the late 1940s and the pioneering works of Banach, Knaster and Steinhaus [Steinhaus, 1949], who developed the associated theory. The related literature contains many interesting problems, with the most celebrated perhaps being the problems of envy-free cake-cutting and equitable cake-cutting, for which a plethora of results have been obtained. More recently, the computer science literature has made a significant contribution in studying the computational complexity of these problems, and attempting to design efficient algorithms for several of their variants [Aziz and Mackenzie, 2016a, b; Deng et al., 2012; Arunachaleswaran et al., 2019].

Another classical problem in fair division, whose study dates back to as early as the 1940s and the work of Neyman , is the Consensus-Halving problem [Simmons and Su, 2003]. In this problem, there is a set of $n$ agents with valuation functions over the $I=$ interval. The goal is to divide the interval into pieces using at most $n$ cuts, and assign a label from $\{+,-\}$ to each piece, such that every agent values the total amount of $I$ labeled “$+$” and the total amount of $I$ labeled “$-$” equally. The name “Consensus-Halving” is attributed to Simmons and Su , although the problem has been studied under different names in the past. For example, it is also known as The Hobby-Rice theorem [Hobby and Rice, 1965], or continuous necklace splitting [Alon, 1987]. Similarly to other well-known problems in fair division, the existence of a solution to the Consensus-Halving problem is always guaranteed, and can be proven via the application of a fixed-point theorem; here the Borsuk-Ulam theorem [Borsuk, 1933]. As a matter of fact, the problem is a continuous analogue of the well-known Necklace Splitting problem [Goldberg and West, 1985; Alon, 1987], whose existence of a solution is typically established via an existence proof for the continuous version.

The Consensus-Halving problem attracted attention in the literature of computer science recently, due to the recent results of Filos-Ratsikas and Goldberg who studied the computational complexity of the approximate version, in which there is a small allowable discrepancy $\varepsilon$ between the values of the two portions. First, in [Filos-Ratsikas and Goldberg, 2018], the authors proved that $\varepsilon$-Consensus-Halving for inverse-exponential $\varepsilon$ is complete for the computational class PPA, defined by Papadimitriou . This was the first PPA-completeness result for a “natural” problem, i.e., a computational problem that does not have a polynomial-sized circuit explicitly in its definition, answering an open question from Papadimitriou , reiterated multiple times over the years [Grigni, 2001; Aisenberg et al., 2020]. Then in [Filos-Ratsikas and Goldberg, 2019], the authors strengthened their hardness result to the case of inverse-polynomial $\varepsilon$, which also established the PPA-completeness of the Necklace Splitting problem for $2$ thieves.

Despite the aforementioned results, the complexity of the problem is not yet well understood. Does the problem remain hard if one restricts attention to classes of simple valuation functions? Note that the reduction of [Filos-Ratsikas and Goldberg, 2018, 2019] uses instances with piecewise constant valuation functions with polynomially many pieces. On the opposite side, are there efficient algorithms for solving special cases of the problem? What if we allow a larger number of cuts?

Towards understanding the complexity of Consensus-Halving, we present the following results.

We prove that $\varepsilon$-Consensus-Halving is PPA-complete, even when the agents have two-block uniform valuations, i.e., valuation functions which are piecewise uniform over the interval and assign non-zero value on at most two pieces. This result holds even when $\varepsilon$ is inverse-polynomial, and extends to the case where the number of allowable cuts is $n+n^{1-\delta}$, for some constant $\delta>0$.

This is an important strengthening of the results in [Filos-Ratsikas and Goldberg, 2018, 2019] which require the agents to have piecewise constant valuations with polynomially many non-uniform blocks. En route to this result, we obtain a significant simplification to the proof of Filos-Ratsikas and Goldberg , which uses new gadgets for the encoding of the circuit of high-dimensional Tucker (see Definition 6), which we reduce from. Our new reduction also gives a simplified proof of PPA-completeness for Necklace Splitting with $2$ thieves [Filos-Ratsikas and Goldberg, 2018, 2019].

We study the case of single-block valuations and provide the first algorithmic results for the problem.To be precise, we provide the first such results for the version of the problem with $n$ agents and $n$ cuts. For a large number of cuts, Brams and Taylor present algorithms for $\varepsilon$-approximate solutions. In fact, very recently and after the publication of the conference version of our paper, Alon and Graur provided the first polynomial-time algorithms for the general $\varepsilon$-Consensus-Halving problem with a limited number of cuts (but still more than $2n$). Specifically, we present:

an algorithm for any $\varepsilon$, whose running time is polynomial in $1/\varepsilon$ and a parameter $d$ related to the maximum number of overlapping blocks.

a polynomial-time algorithm for $1/2$-Consensus-Halving.

As an application of the new ideas developed in our reduction, we obtain the first hardness result for a generalization of $\varepsilon$-Consensus-Halving, known as $\varepsilon$-Consensus-$1/k$-Division, for $k\geq 3$. Specifically, we prove that $\varepsilon$-Consensus-$1/3$-Division is PPAD-hard, when $\varepsilon$ is inverse-exponential.

2 Discussion and Related Work

The study of the Consensus-Halving problem dates back to the early 1940s and the work of Neyman . The first proof of existence for $n$ cuts can be traced back to the 1965 theorem of Hobby and Rice [Hobby and Rice, 1965]. The problem was famously studied in the context of Necklace Splitting, being a continuous analogue of the latter problem; in fact, most known proofs for Necklace Splitting go via the continuous versionThis is true for the case of $2$ thieves. For $k$ thieves, the proofs go via the Consensus-$1/k$-Division problem instead. [Goldberg and West, 1985; Alon and West, 1986]. The name Consensus-Halving is attributed to Simmons and Su , who studied the continuous problem independently, and came up with a constructive proof of existence. Their construction, although yielding an exponential-time algorithm, was later adapted by Filos-Ratsikas et al. to prove that the problem lies in the computational class PPA.

The class PPA was defined by Papadimitriou in his seminal paper in 1994, in which he also defined several other important subclasses of TFNP [Megiddo and Papadimitriou, 1991], the class of Total Search Problems in NP, i.e., problems that always have solutions which are efficiently verifiable. Among those classes, the class PPAD has been very successful in capturing the complexity of many interesting computational problems [Mehta, 2018; Garg et al., 2018; Goldberg and Hollender, 2021; Chen et al., 2017], highlighted by the celebrated results of Daskalakis et al. and Chen et al. about the PPAD-completeness of computing a Nash equilibrium. On the contrary, since the definition of the class, PPA was not known to admit any natural complete problems, but rather mostly versions of PPAD-complete problems of a topological nature, defined on non-orientable spaces [Deng et al., 2021; Grigni, 2001]. In 2015, Aisenberg et al. showed that the computational version of Tucker’s Lemma [Tucker, 1945], already shown to be in PPA by Papadimitriou , is actually complete for the class.

Using the latter result as a starting point, Filos-Ratsikas and Goldberg proved that $\varepsilon$-Consensus-Halving is PPA-complete when $\varepsilon$ is inverse exponential. This was the first PPA-completeness result for a “natural” computational problem, where the term “natural” takes the specific meaning of a problem that does not have a polynomial-sized circuit in its definition. The quest for such problems that would be complete for PPA was initiated by Papadimitriou himself [Papadimitriou, 1994] and was later brought up again by several authors, including Grigni and Aisenberg et al. . In the same paper, the authors also provided a computational equivalence between the $\varepsilon$-Consensus-Halving problem and the well-known Necklace Splitting problem of Alon for $2$ thieves [Goldberg and West, 1985; Alon and West, 1986], when $\varepsilon$ is inverse-polynomial. In [Filos-Ratsikas and Goldberg, 2019], the authors strengthened their result to $\varepsilon$ being inverse-polynomial, which, together with the aforementioned result from [Filos-Ratsikas and Goldberg, 2018], also provided a proof for the PPA-completeness of Necklace Splitting. As we mentioned earlier, besides being a strengthening, our PPA-hardness proof for $\varepsilon$-Consensus-Halving is a notable simplification over that of [Filos-Ratsikas and Goldberg, 2019], and importantly, it holds for $\varepsilon$ which is inverse-polynomial. Therefore, we also obtain a new, simplified proof of PPA-hardness for Necklace Splitting with $2$ thieves.

For constant $\varepsilon$, the only hardness result that we know is the PPAD-hardness of Filos-Ratsikas et al. , who also show that when $n-1$ cuts are allowed, deciding whether a solution exists is NP-hard. Recently, Deligkas et al. studied the complexity of exact Consensus-Halving and showed that the problem is FIXP-hard. Interestingly, the authors also introduced a new computational class, called BU (for Borsuk-Ulam) and showed that the problem lies in that class, leaving open the question of whether it is BU-complete. Very recently, using our new reduction presented in Section 3 as a starting point, Batziou et al. showed that computing a strong approximate solution of Consensus-Halving (with valuations represented by algebraic circuits) is complete for the class $\textup{BU}_{a}$ (the strong approximation version of the class BU).

If we generalize the number of labels to $\{1,2,\ldots,k\}$ rather that $\{+,-\}$, and we allow $(k-1)n$ cuts rather than only $n$, then we obtain a generalization of the Consensus-Halving problem which was referred to as Consensus-$1/k$-Division in [Simmons and Su, 2003]. The existence of a solution for this problem can be proved via fixed-point theorems that generalize the Borsuk-Ulam theorem [Bárány et al., 1981; Alon, 1987], however very little is known about its complexity. One might feel inclined to believe that Consensus-$1/k$-Division is a harder problem that Consensus-Halving; however, note that in the former problem, we have more cuts at our disposal. In fact, Filos-Ratsikas and Goldberg conjectured that the complexities of the problems for different values of $k$ are incomparable, and are characterized by different complexity classes. The complexity classes that are believed to be the most related are called PPA-$k$, defined also by Papadimitriou in his original paper; we refer the reader to the recent papers of [Göös et al., 2020; Hollender, 2021] for a more detailed discussion of these classes. As a matter of fact, in a recent paper we have shown [Filos-Ratsikas et al., 2021] that the problem is in PPA-$k$, for any $k$ which is a prime power.

Before our paper, virtually nothing was known about the hardness of the problem when $k\geq 3$. While the techniques in [Filos-Ratsikas and Goldberg, 2019] were highly reliant on the presence of only two labels, our ideas do carry over to the case when $k=3$, which enables us to prove our PPAD-hardness result. While we do not expect the problem for $k\geq 3$ to be PPAD-complete, our proof offers important intuition about the intricacies of the problem and could be useful for proving stronger hardness results in the future.

Preliminaries

We start with the definition of the $\varepsilon$-approximate version of the Consensus-Halving problem.

Let $k\geq 2$. We are given $\varepsilon>0$ and a set $\mathcal{C}$ of continuous probability measures $\mu_{1},\dots,\mu_{n}$ on $I=$. The probability measures are given by their density functions on $I$. The goal is to partition the unit interval into $2$ (not necessarily connected) pieces $I^{+}$ and $I^{-}$ using at most $n$ cuts, such that $|\mu_{j}(I^{+})-\mu_{j}(I^{-})|\leq\varepsilon$ for all agents $j\in\{1,\ldots,n\}$.

We will refer to the probability measures $\mu_{1},\ldots,\mu_{n}$ as valuation functions or simply valuations. While the existence and PPA-membership results hold more generally, in this paper, we will restrict our attention to the case when the valuation functions are piecewise constant. These can be represented explicitly in the input as endpoints and heights of value blocks.

A valuation function $\mu_{i}$ is piecewise constant over an interval $I$, if the domain can be partitioned into a finite set of intervals such that the density of $\mu_{i}$ is constant over each interval.

Piecewise constant functions are often referred to as step functions.

We will consider the following subclasses of piecewise constant valuation functions.

Piecewise Uniform:, The domain can be partitioned into a finite set of intervals such that the density of $\mu_{i}$ is either $v_{i}$ or over each interval, for some constant $v_{i}$.

$d$-block Uniform: The domain can be partitioned into a finite set of intervals, such that in at most $d$ of those the density of $\mu_{i}$ is $v_{i}$ and everywhere else it is , for some constant $v_{i}$.

$2$-block Uniform: $d$-block uniform valuations for $d=2$.

Single-block: $d$-block uniform valuations for $d=1$. Here we omit the term “uniform”, as there is only a single value block.

Obviously, piecewise constant $\supseteq$ piecewise uniform $\supseteq$ $2$-block uniform $\supseteq$ single-block.

As we mentioned in the introduction, Consensus-Halving is a Total Search Problem in NP, i.e., a problem with a guaranteed solution which is verifiable in polynomial time. The corresponding class is the class TFNP [Megiddo and Papadimitriou, 1991]. Formally, a binary relation $P(x,y)$ is in the class TFNP if for every $x$, there exists a $y$ of size bounded by a polynomial in $|x|$ such that $P(x,y)$ holds and $P(x,y)$ can be verified in polynomial time. The problem is given $x$, to find such a $y$ in polynomial time.

The subclasses of TFNP that will be relevant for this paper are PPAD and PPA [Papadimitriou, 1994]. These are defined via their canonical problems, End-of-Line and Leaf respectively.

The input to the End-of-Line problem consists of two Boolean circuits $S$ (for successor) and $P$ (for predecessor) with $n$ inputs and $n$ outputs such that $P(0^{n})=0^{n}\neq S(0^{n})$, and the goal is to find a vertex $x$ such that $P(S(x))\neq x$ or $S(P(x))\neq x\neq 0^{n}$.

A problem is in PPAD if it is polynomial-time reducible to End-Of-Line and it is PPAD-complete if End-Of-Line reduces to it in polynomial-time. Intuitively, PPAD is defined with respect to a directed graph of exponential size, which is given implicitly as input, via the use of the predecessor and successor circuits defined above. PPAD is a subclass of PPA, which is defined similarly, but with respect to an undirected graph and a circuit that outputs the neighbours of a vertex. Its canonical computational problem is called Leaf, which is defined below.

The input to the Leaf problem is a Boolean circuit $C$ with $n$ inputs and at most $2n$ outputs, outputting the set $\mathcal{N}(y)$ of (at most two) neighbors of a vertex $y$, such that $|\mathcal{N}(0^{n})|=1$, and the goal is to find a vertex $x$ such that $x\neq 0^{n}$ and $|\mathcal{N}(x)|=1$.

A problem is the class PPA if it is polynomial-time reducible to Leaf and is PPA-complete if Leaf reduces to it in polynomial time.

2 High-dimensional Tucker

Our reduction in Section 3 will start from the following problem, which is an $N$-dimensional variant of the $2D$-Tucker problem [Papadimitriou, 1994; Aisenberg et al., 2020].

An instance of high-D-Tucker consists of a labeling $\lambda:^{N}\to\{\pm 1,\dots,\pm N\}$ computed by a Boolean circuit. We further assume that the labeling is antipodally anti-symmetric (i.e. for all $x$ on the boundary of $^{N}$ it holds that $\lambda(\overline{x})=-\lambda(x)$ where $\overline{x}_{i}=9-x_{i}$ for all $i$), which can be enforced syntactically. A solution consists of two points $x,y\in^{N}$ with $\lambda(x)=-\lambda(y)$ and $\|x-y\|_{\infty}\leq 1$.

Filos-Ratsikas and Goldberg showed that the problem is PPA-hard, when the domain is $^{N}$ instead of $^{N}$. We adapt the hardness to the case of Definition 6 in the theorem below.

Papadimitriou has shown that the problem lies in PPA. In order to show PPA-hardness, we use the fact that Filos-Ratsikas and Goldberg have proved that the problem is PPA-hard on the domain $^{N}$ (instead of $^{N}$) by using a standard snake-embedding technique [Chen et al., 2009; Deng et al., 2017].

Let $\lambda$ be an instance of High-D-Tucker but on the domain $^{N}$ instead of $^{N}$. We will reduce this to an instance $\lambda^{\prime}$ of High-D-Tucker (on our standard domain $^{N}$). In the two-dimensional case ($N=2$), the high level idea of the reduction is to take the domain $^{N}$ and duplicate the central vertical and horizontal lines of the grid (thus also duplicating the labels at these grid points).

Formally, we proceed as follows. Define the operator $\widehat{\cdot}$ such that for any $r\in$

Then, for any $x=(x_{1},\dots,x_{N})\in^{N}$, let $\widehat{x}=(\widehat{x}_{1},\dots,\widehat{x}_{N})\in^{N}$. Now define $\lambda^{\prime}$ such that for all $x\in^{N}$, $\lambda^{\prime}(x):=\lambda(\widehat{x})$. This is well-defined and given a circuit that computes $\lambda$, we can construct a circuit for $\lambda^{\prime}$ in polynomial time.

Let us first show that if $\lambda$ is antipodally anti-symmetric on $^{N}$, then $\lambda^{\prime}$ is antipodally anti-symmetric on $^{N}$. Consider any $x\in\partial(^{N})$, i.e. there exists $j\in[N]$ such that $x_{j}\in\{1,8\}$. Note that we then have $\widehat{x}\in\partial(^{N})$, because $\widehat{x}_{j}\in\{1,7\}$. Thus, we know that $\lambda(8-\widehat{x}_{1},\dots,8-\widehat{x}_{N})=-\lambda(\widehat{x}_{1},\dots,\widehat{x}_{N})$. Using the key observation that $\widehat{9-x_{i}}=8-\widehat{x}_{i}$ for all $i\in[N]$, we obtain that

It remains to show that given any solution to $\lambda^{\prime}$, we can retrieve in polynomial time a solution to $\lambda$. Let $x,y\in^{N}$ be such that $\lambda^{\prime}(x)=-\lambda^{\prime}(y)$ and $\|x-y\|_{\infty}\leq 1$. Then, we immediately obtain that $\lambda(\widehat{x})=-\lambda(\widehat{y})$ and it remains to show that $\|\widehat{x}-\widehat{y}\|_{\infty}\leq 1$. Consider any $i\in[N]$. If $x_{i},y_{i}\geq 5$ or if $x_{i},y_{i}\leq 4$, then in both cases $|x_{i}-y_{i}|\leq 1$ implies $|\widehat{x}_{i}-\widehat{y}_{i}|\leq 1$. If $x_{i}\geq 5$ and $y_{i}\leq 4$, then $|x_{i}-y_{i}|\leq 1$ implies that $x_{i}=5$ and $y_{i}=4$ and we get $|\widehat{x}_{i}-\widehat{y}_{i}|=0\leq 1$. The remaining case is analogous. Thus, we have shown that $\widehat{x},\widehat{y}$ form a solution to $\lambda$. ∎

Consensus-Halving with two-block uniform valuations is PPA-hard

In this section, we present our first result, regarding the PPA-hardness of Consensus-Halving.

$\varepsilon$-Consensus-Halving is PPA-hard, when $\varepsilon$ is inverse-polynomial and the agents have two-block uniform valuations.

As we mentioned in the Introduction, Theorem 2 is a strengthening of the result of Filos-Ratsikas and Goldberg , which requires the valuation functions to have a polynomial number of value blocks, and which is seemingly very difficult to extend to two-block uniform valuations. To achieve this stronger result, we have to develop new gadgetry, based on a new interpretation of the cut positions with respect to the positions of points in the domain of high-D-Tucker. As it turns out, this new interpretation allows us to obtain a new proof of the main theorem of Filos-Ratsikas and Goldberg , one which is conceptually much simpler, even though it actually applies to more restricted valuations.

Before we proceed, we first remark the following. In [Filos-Ratsikas et al., 2018] (where the PPAD-hardness of $\varepsilon$-Consensus-Halving was proven for constant $\varepsilon$) the authors presented a simple argument that allowed them to extend their hardness result to $n+c$ cuts, where $c$ is some constant. The idea is to make $c+1$ completely disjoint copies of the instance of $\varepsilon$-Consensus-Halving, and solve it using $n+c$ cuts. One of the copies would have to be solved using at most $n$ cuts, which is a PPAD-hard problem. We observe that the same principle applies generically (beyond PPAD-hardness and also to the results of Filos-Ratsikas and Goldberg ), and in fact extends to $n+n^{1-\delta}$ cuts, where $\delta>0$ is some constant. From Theorem 2, we obtain the following corollary.

$\varepsilon$-Consensus-Halving is PPA-hard, when $\varepsilon$ is inverse polynomial and the agents have two-block uniform valuations, even when one is allowed to use $n+n^{1-\delta}$ cuts, for constant $\delta>0$.

We are now ready to prove Theorem 2. We first provide an overview of the reduction and we highlight the main simplifications over the proof of Filos-Ratsikas and Goldberg . Then we proceed to formally present the proof of Theorem 2.

We are given an instance of high-D-Tucker, namely a labeling $\lambda:^{N}\to\{\pm 1,\dots,\pm N\}$ computed by a Boolean circuit. We will show how to construct an instance of Consensus-Halving in polynomial time such that any $\varepsilon$-approximate solution yields a solution to the high-D-Tucker instance (for some inversely-polynomial $\varepsilon$). The complexity will be measured with respect to the representation size of the high-D-Tucker instance, i.e., the size of the circuit $\lambda$ (which is also at least $N$).

For clarity and convenience, the instance of Consensus-Halving we will construct will not be defined on the domain $$, but instead on some interval$[0,M]$, where$M$is bounded by a polynomial in the size of the high-D-Tucker circuit$\lambda$. It is easy to transform this into an instance on$$by just re-scaling the valuation functions, namely scaling down the positions of the blocks by$M$and scaling up the heights of the blocks by$M$.

Let us first provide a very high-level description of the instance we construct. Similarly to [Filos-Ratsikas and Goldberg, 2019], the left-most end of the instance will be the Coordinate-Encoding region. In any solution $S$ to the instance, the way in which this region is divided amongst the labels $+$ and $-$ will represent a point $x\in^{N}$. A circuit-simulator $C$ will read-in the coordinates of $x$, perform some computations (including a simulation of $\lambda$) and output $N$ values $[C(x)]_{1},\dots,[C(x)]_{N}\in$. This circuit-simulator will be implemented by a set of agents where each agent will enforce one gate/operation of the circuit. Unfortunately, the circuit-simulator can sometimes fail to perform the desired computation, so instead of one circuit-simulator $C$ we will actually have a polynomial number $p(N)$ of circuit-simulators $C_{1},\dots,C_{p(N)}$. Each of these circuit-simulators will be performing (almost) the same computation. Finally, we will introduce a Feedback region where $N$ feedback agents $f_{1},\dots,f_{N}$ will implement the feedback mechanism. For each $i\in\{1,\dots,N\}$, feedback agent $f_{i}$ will ensure that $\frac{1}{p(N)}\sum_{j=1}^{p(N)}[C_{j}(x)]_{i}\approx 0$. Namely, it will ensure that the average of the outputs in dimension $i$ is close to zero. We will show that from any solution $S$ to the Consensus-Halving instance, we obtain a solution to the original high-D-Tucker instance. To be a bit more precise, from the point $x\in^{N}$ encoded by the Coordinate-Encoding region in a solution $S$, we will be able to extract a polynomial number of points on the high-D-Tucker grid, with the guarantee that two of these points form a solution (which can then be identified efficiently).

The sub-interval $[0,N]$ of the domain is called the Coordinate-Encoding region. Indeed, the way in which this region is subdivided amongst the $+$ and $-$ labels in a solution $S$ will encode the coordinates of a point in $x\in^{N}$. In more detail, $x_{1}\in$ will be given by $v()$, i.e., the value encoded by interval $$. Similarly,$x_{2}\in$will be given by$v()$,$x_{3}\in$by$v()$, etc.

The sub-interval $[N,N+p(N)]$ of the domain is called the Constant-Creation region. This region will be used to create the constants that the circuit-simulators need. The circuit-simulator $C_{1}$ will read-in the value $v([N,N+1])=:\textup{const}_{1}$ and will assume that it corresponds to the value $+1$. Note that given the constant $+1$, the circuit-simulator can create any constant $\zeta\in$ by using a $\times\zeta$-gate (multiplication by the constant $\zeta$). Similarly, the circuit-simulator $C_{2}$ will read-in the value $v([N+1,N+2])=:\textup{const}_{2}$ and use it as the constant $+1$, and so on for $C_{3},C_{4},\dots,C_{p(N)}$.

If $S$ is a solution such that the Constant-Creation region does not contain any cut, then the whole region will have the same label, and without loss of generality we can assume that this label is $+$. Thus, in such a solution $S$, all the circuit-simulators will indeed read-in the constant $+1$ from the Constant-Creation region, i.e., we will indeed have $\textup{const}_{j}=+1$ for all $j=1,\dots,p(N)$.

For each $j\in\{1,2,\dots,p(N)\}$, the sub-interval $[N+p(N)+(j-1)q,N+p(N)+jq]$ of the domain will be used by the circuit-simulator $C_{j}$. The length $q$ used by every circuit-simulator will be upper-bounded by some polynomial in $N$ and the size of the circuit $\lambda$. Every circuit-simulator $C_{j}$ will read-in the coordinates $x_{1},\dots,x_{N}\in$ of the point $x$ from the Coordinate-Encoding region, as well as the value $\textup{const}_{j}\in$ from the Constant-Creation region (and assume that it corresponds to the constant $+1$). Using these values, $C_{j}$ will perform some computations, including a simulation of the Boolean circuit $\lambda$, and finally output $N$ values $[C_{j}(x,\textup{const}_{j})]_{1},\dots,[C_{j}(x,\textup{const}_{j})]_{N}\in$ into the Feedback region.

The Feedback region is located at the right end of the domain and is subdivided into $N$ intervals $F_{1},\dots,F_{N}$ of length $p(N)$ each. For every $j\in[p(N)]$, let $F_{i}(j)$ denote the $j$th sub-interval of length $1$ of $F_{i}$. The $i$th output of circuit-simulator $C_{j}$ will be located in sub-interval $F_{i}(j)$. In other words, $v(F_{i}(j))=[C_{j}(x,\textup{const}_{j})]_{i}$.

Every interval $F_{i}$ will have a corresponding feedback agent $f_{i}$, who will ensure that the average of all the outputs in interval $F_{i}$ is close to zero. In more detail, agent $f_{i}$ will have a single block of value that covers interval $F_{i}$. As a result, this agent will be satisfied only if $\frac{1}{p(N)}\sum_{j=1}^{p(N)}v(F_{i}(j))\in[-\varepsilon,\varepsilon]$.

Any agent belonging to a circuit-simulator performs a gate operation. In Section 3.3, we introduce the different types of gates and how they are implemented by agents. One important feature of the agents implementing the gates is that every such agent ensures that at least one cut must lie in a specific interval $J$ of the domain (in any solution $S$). By construction, we will make sure that these intervals are pairwise disjoint for different agents. Thus, every agent introduced as part of a circuit-simulator will force one cut to lie in a specific interval.

The only agents that are not part of a circuit-simulator are the feedback agents $f_{1},\dots,f_{N}$. Since the number of cuts in any solution is at most the number of agents, there are at most $N$ cuts that are not constrained to lie in some specific interval. We call these the free cuts. The free cuts can theoretically “go” anywhere in the domain and interfere with the correct functioning of the circuit-simulators or the Constant-Creation region. The expected behavior of these $N$ free cuts is that they should lie in the Coordinate-Encoding region. As such, any of the free cuts that lies outside the Coordinate-Encoding region will be called a stray cut (following [Filos-Ratsikas and Goldberg, 2019]).

If there is at least one stray cut, then the point $x\in^{N}$ encoded by the Coordinate-Encoding region lies on the boundary of $^{N}$ (i.e., there exists $i$ such that $|x_{i}|=1$).

There are two ways for a stray cut to cause trouble:

it can corrupt a circuit, i.e., interfere with the correct functioning of the gates of a circuit-simulator. If the cut lies in the region of circuit-simulator $C_{j}$, then it can make a gate output the wrong result (i.e., not perform the desired operation). If the cut lies in the Constant-Creation region and intersects the interval that is used by circuit-simulator $C_{i}$ to read-in the constant $\textup{const}_{j}$, then it can have an effect such that $|\textup{const}_{j}|\neq 1$. However, in any case, a single stray cut can only interfere with one circuit-simulator in this way. Thus, at most $N$ circuit-simulators can suffer from this kind of interference. We will choose $p(N)$ large enough so that these corrupted circuit-simulators have a very limited influence.

it can interfere with the sign of $\textup{const}_{j}$ for many circuit-simulators $C_{j}$. Indeed, even a single stray cut can ensure that half of our circuit-simulators read-in the constant $+1$ and the other half read-in the constant $-1$. We will show that this is actually not a problem, and that it does not produce bogus solutions. Since stray cuts can only occur when $x$ lies on the boundary of $^{N}$ (1), the Tucker boundary conditions will be important for this.

Stray cuts that end up in the Feedback region do not have any effect. Indeed, the feedback agents $f_{1},\dots,f_{N}$ are immune to stray cuts. They always ensure that the average of the outputs is close to zero. Thus, a stray cut can only influence the outputs that a feedback agent sees (as detailed above), but not its functionality.

There are two ways in which a circuit-simulator can fail to have the desired output:

it is corrupted by a stray cut. This can happen to at most $N$ circuit-simulators.

it can fail in extracting the binary bits from (a point close to) $x$. We will ensure that this can happen to at most $N$ circuit-simulators.

Thus, at most $2N$ circuit-simulators fail, i.e., at least $p(N)-2N$ circuit-simulators have the desired output.

2 Major simplifications compared to the previous proof

The major simplifications compared to the previous proof of Filos-Ratsikas and Goldberg are as follows:

The PPA-hardness of high-D-Tucker was already established in [Filos-Ratsikas and Goldberg, 2019] and our version can be obtained from that one using minor modifications, see Theorem 1. The corresponding result of [Filos-Ratsikas and Goldberg, 2019] is a standard application of the “snake-embedding” technique developed in [Chen et al., 2009]. However, the reduction in [Filos-Ratsikas and Goldberg, 2019] requires (a) a further constraint on how the domain is colored and more importantly (b) the embedding of the high-D-Tucker instance into a Möbius-type simplex domain, in which two facets have been “identified” with each other - one can envision a high-dimensional Möbius strip with an instance of high-D-Tucker in its center, embedding in a high-dimensional simplex. A key step in the reduction is the extension of the labeling of high-D-Tucker to the remainder of the domain, in a way that does not introduce any artificial solutions, and such that solutions to high-D-Tucker can be traced back from solutions on other points on the domain. For this purpose, the authors of [Filos-Ratsikas and Goldberg, 2019] develop a rather complicated coordinate transformation, applied to the inputs read from the positions of the cuts. They establish how to compute the transformation and its inverse in polynomial time and how distances in the two coordinate systems (before and after the transformation) are polynomially related. In contrast, our reduction works with the rather clean domain of high-D-Tucker, avoiding all the unnecessary technical clutter of the domain used in [Filos-Ratsikas and Goldberg, 2019].

Another complication of the proof in [Filos-Ratsikas and Goldberg, 2019] is the use of blanket-sensor agents, which constrain the positions of the cuts in the coordinate-encoding region, to ensure that solutions to $\varepsilon$-Consensus-Halving do not encode points that lie too far from a specific region in the “middle” of the domain, called the “significant region”; this is achieved via appropriate feedback provided by these agents to the coordinate-encoding agents. To make sure that the blanket-sensor agents do not “cancel” each other, extra care must be taken on how the feedback of these agents is designed, giving rise to a series of technical lemmas. Our reduction does not need to use any such agents and is therefore significantly simpler in that regard as well.

The reduction in [Filos-Ratsikas and Goldberg, 2019] requires knowledge of the label sequence, i.e., whether the first cut that occurs in the c-e region has the label $+$ or $-$ on its left side. This is fundamental for the design of the gates, as they read the inputs as the distances from the left endpoints of the corresponding designated intervals, unlike our interpretation, which measures the difference between the value of the two labels. Thus, for the disorientation of the domain and to deal with sign flips that happen due to the stray cuts, the authors of [Filos-Ratsikas and Goldberg, 2019] employ a pre-processing circuit that uses the first coordinate-detecting agent as a reference agent, when performing computations. This is again not needed in our case; our equivariant gates ensure that even when the corresponding point lies on the boundary of the high-D-Tucker domain, the output is computed correctly in a much simpler way.

3 Arithmetic Gates

In this section we show how to construct gates which perform various operations on numbers in $$with error at most$g(\varepsilon)=16\varepsilon$, where$\varepsilon$ is the error we allow in a Consensus-Halving solution. Some of these gates will be immune to “corruption” by a stray cut, while others might get corrupted and not work properly.

Let $\delta\in[2\varepsilon,1]$. Let $I$ and $O$ be disjoint intervals of length $1$. The agent for this gate has a block of length $1-\delta$ and height $\frac{1}{2-\delta}$ centered in interval $I$ and a block of length $1$ and (same) height $\frac{1}{2-\delta}$ in interval $O$.

It is easy to check that since $\delta\geq 2\varepsilon$, at least one cut must lie strictly within $O$ in any solution. Furthermore, this gate has the notable property that it cannot be corrupted. From this construction, we obtain the following gates:

Multiplication by $-1$ $[G_{\times(-1)}]$: Set $\delta=2\varepsilon$. Then, in any solution it holds that $v(O)=T[-v(I)\pm 4\varepsilon]$. See Fig. 2 for an illustration.

For $\zeta\leq 0$, we let $\delta=\max(1+\zeta,2\varepsilon)$ and obtain that $v(O)=T[\zeta\pm 4\varepsilon]$.

For $\zeta>0$, use $G_{-\zeta}$ and then $G_{\times(-1)}$, for a total error of at most $8\varepsilon$. Note that if $|v(I)|=1$, then this gate can also be used to obtain $T[v(I)\times\zeta\pm 8\varepsilon]$.

[G_{+}]: Let $I_{1}$ and $I_{2}$ be the two length-$1$ intervals encoding the two inputs. Let $I^{\prime}$ be an interval of length $2$ that is disjoint from $I_{1}$ and $I_{2}$. Let $J$ be an interval of length $3$ that is disjoint from $I_{1},I_{2}$ and $I^{\prime}$. We first use a $G_{\times(-1)}$-gate with input $I_{1}$ and output $I^{\prime}$, and another one with input $I_{2}$ and output $I^{\prime}$.

To compute addition we create a new agent with valuation function that has height $1/5$ in $I^{\prime}$ and in $J$, and height everywhere else. Note that since $\varepsilon<1/5$, in any solution there must be a cut in $J$. We say that the gate is corrupted, if there are at least two cuts lying strictly in the interval $J$. The output of the gate will be in interval $O=J$. If the gate is not corrupted, then by construction we have $v(O)=T[v(I_{1})+v(I_{2})\pm 16\varepsilon]$. See Fig. 4 for an illustration.

3.2 Additional Gates

Using the gates presented above, we can also implement the following operations.

We can copy a value by using two successive $G_{\times(-1)}$-gates. The error will be at most $8\varepsilon$. This gate can not be corrupted.

This can be implemented by a chain of $k-1$ additions that repeatedly add the input to the intermediate summation. It is easy to check that the error is at most $(k-1)16\varepsilon$.

For the Boolean gates, the bits $\{0,1\}$ will be represented by the values $-1$ (for ) and $+1$ (for $1$). We say that an input value $v(I)\in$ is a perfect bit, if $v(I)\in\{-1,1\}$. The Boolean gates we will construct have the following very nice property: if all inputs are perfect bits, then the output is a perfect bit (and is the correct output).

Negation Gate $[G_{\lnot}]$:. This can be done by first using a $G_{\times(-1)}$-gate and then a $G_{\times 2}$-gate. The error will be at most $20\varepsilon$, so this will work as intended as long as $20\varepsilon\leq 1$.

AND Gate: $[G_{\land}]$: Let $b_{1}$ and $b_{2}$ be the two inputs. We perform the computation $((b_{1}+b_{2})-1/2)\times 4$ by using two $G_{+}$-gates, a $G_{-1/2}$-gate and a $G_{\times 4}$-gate. The error will be at most $12\times 16\varepsilon$, so the gate will work as intended as long as $12\times 16\varepsilon\leq 1$.

OR Gate $[G_{\lor}]$: This can easily be obtained by using $G_{\land}$ and $G_{\lnot}$.

Note that all the arithmetic gates we have presented have error at most $g(\varepsilon)=16\varepsilon$, with the exception of $G_{\times k}$, which has an error of $(k-1)g(\varepsilon)$. Thus, we have to be careful whenever we use this gate for some non-constant $k$.

Note that the operation performed by any gate is equivariant. Namely, if we flip the sign of all inputs, the same output is still valid, but with a flipped sign. For $G_{\times-1}$ and $G_{+}$ gates this is obvious. For $G_{\zeta}$, we have to recall that $\textup{const}_{j}$ is the input to the gate. With this interpretation, the equivariance is once again obvious. For the $G_{\land}$-gate the equivariance is a bit more subtle. Note that it uses a $G_{-1/2}$-gate, which uses $\textup{const}_{j}$. Thus, in this case again, if we flip the sign of the inputs $b_{1}$, $b_{2}$ and $\textup{const}_{j}$, the sign of the output is flipped too.

This property of the gates is not a coincidence. It follows from the way we are encoding values. Note that in any solution $S$, if we swap the labels $+$ and $-$, the solution remains valid. The only thing that has changed is that for any gate, the sign of all inputs and outputs has been flipped.

It follows that any circuit that we construct out of these gates will be equivariant. Namely, the computation will still be valid if we flip the sign of all inputs (including $\textup{const}_{j}$) and all outputs.

4 Circuit-Simulators

In this section we describe the functionality of the circuit-simulators and what it achieves. Recall that every circuit-simulator $C_{j}$ reads-in inputs $x_{1},\dots,x_{N}\in$ from the Coordinate-Encoding region and $\textup{const}_{j}\in$ from the Constant-Creation region. The circuit-simulator then performs some computations and outputs $[C_{j}(x,\textup{const}_{j})]_{1},\dots,[C_{j}(x,\textup{const}_{j})]_{N}\in$ into the Feedback region. If the circuit-simulator $C_{j}$ is corrupted (i.e., one of the stray cuts interferes with it), then we will not claim anything about the outputs of $C_{j}$. In that case, we will only use the fact that all the outputs must lie in $$ (which is guaranteed by the way values are represented).

If the circuit-simulator $C_{j}$ is not corrupted, then we know that all gates will perform correct computations, and we also know that $\textup{const}_{j}\in\{-1,+1\}$. In our construction of $C_{j}$, we will be assuming that $\textup{const}_{j}=+1$. However, we will show later that even if $\textup{const}_{j}=-1$, $C_{j}$ will output something useful.

In the first phase, $C_{j}$ applies a small displacement to its input $x$. Namely, for every $i\in[N]$, $C_{j}$ computes $\widehat{x}_{i}\approx T[x_{i}+j\alpha]$, where $\alpha=\frac{1}{16p(N)}$. This is achieved by using a $G_{j\alpha}$-gate to create the constant $j\alpha$ (by using $\textup{const}_{j}$), followed by a $G_{+}$-gate to perform the addition $x_{i}+j\alpha$. However, since $\varepsilon>0$, the gates might make some error in the computations. Nevertheless, by construction of the gates, we immediately obtain:

Assume that the circuit-simulator $C_{j}$ is not corrupted and $\textup{const}_{j}=+1$. Then the equi-angle displacement phase outputs $\widehat{x}_{i}=T[x_{i}+j\alpha\pm 2g(\varepsilon)]$ for all $i$.

In the second phase, $C_{j}$ extracts the three most significant bits from each $\widehat{x}_{i}\in$. These three bits tell us where $\widehat{x}_{i}$ lies in $$, namely in which of the eight possible standard intervals of length$1/4$:$[-1,-3/4]$,$[-3/4,-1/2]$,$[-1/2,-1/4]$,$[-1/4,0]$,$[0,1/4]$,$[1/4,1/2]$,$[1/2,3/4]$,$[3/4,1]$. Instead of the usual$\{0,1\}$, our bits will take values in$\{-1,+1\}$. The first bit$b_{1}\in\{-1,+1\}$indicates whether$\widehat{x}_{i}$is positive or negative. If$b_{1}=+1$, then$\widehat{x}_{i}\in$. If$b_{1}=-1$, then$\widehat{x}_{i}\in$. The second bit$b_{2}\in\{-1,+1\}$, then indicates in which half of that interval$\widehat{x}_{i}$lies. Thus, if$b_{1}=+1$and$b_{2}=-1$, then$\widehat{x}_{i}\in[0,1/2]$. Note that some of the bits are not well-defined if$\widehat{x}_{i}\in B$where$B=\{-3/4,-1/2,-1/4,0,1/4,1/2,3/4\}$. Thus, we cannot expect the bit extraction to succeed in this case. In fact, the bit extraction will fail if$\widehat{x}_{i}$is sufficiently close to any point in$B$.

The bit extraction for $\widehat{x}_{i}$ is performed as follows.

$b_{1}\approx T[\widehat{x}_{i}\times\lceil 1/g(\varepsilon)\rceil]$ (use $G_{\times\lceil 1/g(\varepsilon)\rceil}$-gate)

$\widehat{x}_{i}^{\prime}\approx T[\widehat{x}_{i}-b_{1}/2]$ (use $G_{-1/2}$-gate and $G_{+}$-gate)

$b_{2}\approx T[\widehat{x}_{i}^{\prime}\times\lceil 1/g(\varepsilon)\rceil]$

$\widehat{x}_{i}^{\prime\prime}\approx T[\widehat{x}_{i}^{\prime}-b_{2}/4]$

$b_{3}\approx T[\widehat{x}_{i}^{\prime\prime}\times\lceil 1/g(\varepsilon)\rceil]$

Note that to compute $-b_{1}/2$ and $-b_{2}/4$ we just use the corresponding constant gate, namely $G_{-1/2}$ and $G_{-1/4}$ (with input $b_{1}$ or $b_{2}$ respectively, instead of $\textup{const}_{j}$). The computation may be incorrect if $b_{1}$ or $b_{2}$ are not in $\{-1,1\}$, but in that case the bit-extraction has already failed anyway.

We can show that the bit-extraction succeeds if $\widehat{x}_{i}$ is sufficiently far away from any point in $B$. Letting $\textup{dist}(t,B)=\min_{p\in B}|t-p|$, we obtain:

Assume that the circuit-simulator $C_{j}$ is not corrupted and $\textup{const}_{j}=+1$. If $\textup{dist}(T[x_{i}+j\alpha],B)\geq 8g(\varepsilon)$, then the bit-extraction phase for $\widehat{x}_{i}$ outputs the correct bits for $T[x_{i}+j\alpha]$.

Since $\textup{dist}(T[x_{i}+j\alpha],B)\geq 8g(\varepsilon)$, it follows by 1 that $\textup{dist}(\widehat{x}_{i},B)\geq 6g(\varepsilon)$, and in particular $|\widehat{x}_{i}|\geq 6g(\varepsilon)$. In step 1 we use a $G_{\times\lceil 1/g(\varepsilon)\rceil}$-gate on input $\widehat{x}_{i}$. By construction of the gate, it follows that $b_{1}=T[\widehat{x}_{i}\times\lceil 1/g(\varepsilon)\rceil\pm(\lceil 1/g(\varepsilon)\rceil-1)g(\varepsilon)]=T[\widehat{x}_{i}\times\lceil 1/g(\varepsilon)\rceil\pm 1]$ where we used $|(\lceil 1/g(\varepsilon)\rceil-1)g(\varepsilon)|\leq 1$. Since $|\widehat{x}_{i}|\geq 6g(\varepsilon)$, it holds that $|\widehat{x}_{i}\times\lceil 1/g(\varepsilon)\rceil|\geq 6\geq 2$. Thus, $b_{1}\in\{-1,+1\}$ is the correct bit for $\widehat{x}_{i}$.

In step 2 we compute $\widehat{x}_{i}^{\prime}=T[\widehat{x}_{i}-b_{1}/2\pm 2g(\varepsilon)]$. Thus, we have $\textup{dist}(\widehat{x}_{i}^{\prime},B)\geq 4g(\varepsilon)$, and in particular $|\widehat{x}_{i}^{\prime}|\geq 4g(\varepsilon)$, which implies that $b_{2}=T[\widehat{x}_{i}^{\prime}\times\lceil 1/g(\varepsilon)\rceil\pm 1]\in\{-1,+1\}$ is the correct first bit for $\widehat{x}_{i}^{\prime}$ and the correct second bit for $\widehat{x}_{i}$.

In step 4 we compute $\widehat{x}_{i}^{\prime\prime}=T[\widehat{x}_{i}^{\prime}-b_{2}/2\pm 2g(\varepsilon)]$. Thus, $|\widehat{x}_{i}^{\prime\prime}|\geq 2g(\varepsilon)$, which implies that $b_{3}=T[\widehat{x}_{i}^{\prime\prime}\times\lceil 1/g(\varepsilon)\rceil\pm 1]\in\{-1,+1\}$ is the correct first bit for $\widehat{x}_{i}^{\prime\prime}$, i.e., the correct second bit for $\widehat{x}_{i}^{\prime}$ and the correct third bit for $\widehat{x}_{i}$.

Finally, note that if $\textup{dist}(T[x_{i}+j\alpha],B)\geq 8g(\varepsilon)$, then $T[x_{i}+j\alpha]$ and $\widehat{x}_{i}$ must lie in the same standard interval of length $1/4$, i.e., they must have the same three bits. ∎

Recall that $\lambda:^{N}\to\{\pm 1,\dots,\pm N\}$ is the Boolean circuit computing the high-D-Tucker labeling. We interpret $$as a subdivision of$$ into standard intervals of length $1/4$. Namely, $1$ corresponds to $[-1,-3/4]$, $2$ to $[-3/4,-1/2]$, etc. Thus, $^{N}$ can be interpreted as a subdivision of $^{N}$ into hypercubes of side-length $1/4$. With this in mind, we define $\overline{\lambda}:(\setminus B)^{N}\to\{\pm 1,\dots,\pm N\}$, so that for any $x\in(\setminus B)^{N}$, $\overline{\lambda}(x)$ is the label that $\lambda$ assigns to the hypercube containing $x$.

We can assume that the inputs of $\lambda$ consist of three bits each, such that the number represented by these three bits yields an element in $$(by using$\equiv\{0,1,\dots,7\}$). The three bits$b_{1},b_{2},b_{3}\in\{-1,+1\}$extracted from$T[x_{i}+j\alpha]$tell us exactly in which interval$T[x_{i}+j\alpha]$lies. Note that if we were to map those bits to$\{0,1\}$(where$-1\mapsto 0$and$+1\mapsto 1$), then the bit-string$b_{1}b_{2}b_{3}$ would correspond to the number associated with the interval and would thus be the correct corresponding input to the circuit.

We re-interpret the circuit $\lambda$ as working on bits $\{-1,+1\}$, where $-1$ corresponds to . Clearly, we can implement this circuit in $C_{j}$ with our Boolean gates. As long as the inputs to every gate are perfect bits (i.e., in $\{-1,+1\}$), the output of the gate will also be a perfect bit, and will correspond to the result of the operation computed by the gate. The inputs to the circuit will be exactly the bits obtained in the bit extraction phase for each $\widehat{x}_{i}$. Thus, it follows that if the bit extraction phase succeeds, then the simulation of $\lambda$ will always have a correct output. In other words, using 2, we obtain:

Assume that the circuit-simulator $C_{j}$ is not corrupted and $\textup{const}_{j}=+1$. If $\textup{dist}(T[x_{i}+j\alpha],B)\geq 8g(\varepsilon)$ for all $i\in[N]$, then the simulation phase outputs $\overline{\lambda}(T[x+j\alpha])$.

$\overline{\lambda}_{i}(z)=+1$ if $\overline{\lambda}(z)=+i$

$\overline{\lambda}_{i}(z)=-1$ if $\overline{\lambda}(z)=-i$

Then, by 3 we obtain that $T[y_{i}^{a}+y_{i}^{b}]=\overline{\lambda}_{i}(T[x+j\alpha])$.

In this last phase, for each $i\in[N]$ we compute $T[y_{i}^{a}+y_{i}^{b}]$ and copy this value into the Feedback region, namely into interval $F_{i}(j)$ (recall that $C_{j}$ is the current circuit-simulator). For this we first use a $G_{+}$-gate and then a $G_{\textup{copy}}$-gate. Thus, we immediately obtain:

Assume that the circuit-simulator $C_{j}$ is not corrupted and $\textup{const}_{j}=+1$. If $\textup{dist}(T[x_{i}+j\alpha],B)\geq 8g(\varepsilon)$ for all $i\in[N]$, then $[C_{j}(x,\textup{const}_{j})]_{i}:=v(F_{i}(j))=T[\overline{\lambda}_{i}(T[x+j\alpha])\pm 2g(\varepsilon)]$ for all $i\in[N]$.

5 Proof of Correctness

In this section we prove that the reduction works, i.e., from any solution to the Consensus-Halving instance, we can obtain a solution to the original high-D-Tucker instance in polynomial time. In order to do this, we consider two cases and show that we can retrieve a solution in both cases. The first case corresponds to a “well-behaved” solution where there are no stray cuts. The second case corresponds to a solution with stray cuts. In both cases, we show that, if $x$ denotes the point encoded by the Coordinate-Encoding region in a solution of the Consensus-Halving instance, then the set $\{T[x+j\alpha]:j\in\{\pm 1,\dots,\pm p(N)\}\}$ must contain two points that have opposite labels in the original high-D-Tucker instance. Two such points can then easily be extracted in polynomial time by simply computing the labels of all $2p(N)$ points in that set. Note also that all points in the set are very close to each other by construction and so the two selected points will lie in adjacent hypercubes of the high-D-Tucker instance (as defined in Phase 3).

We set $p(N)=4N^{2}$ and pick $\varepsilon$ such that $16g(\varepsilon)\leq\frac{1}{16p(N)}$, i.e., $\varepsilon\leq\frac{1}{2^{14}N^{2}}$.

Let $S$ be any $\varepsilon$-approximate solution for the Consensus-Halving instance. If $S$ does not have any stray cuts, then it yields a solution to the high-D-Tucker instance in polynomial time.

Since there are no stray cuts, none of the circuit-simulators is corrupted. In particular, there is no cut strictly inside the Constant-Creation region. Thus, without loss of generality we can assume that the whole Constant-Creation region is labeled $+$. This means that all circuit-simulators read-in the constant $+1$, i.e., $\textup{const}_{j}=+1$ for all $j$.

Since the circuit-simulators are not corrupted, the only way in which they can fail is if the bit extraction phase fails. Let $x\in^{N}$ be the point represented by the Coordinate-Encoding region in $S$. Let $z^{(j)}=T[x+j\alpha]$.

Since $p(N)\alpha\leq 1/16$ and $\alpha=\frac{1}{16p(N)}\geq 16g(\varepsilon)$, it follows that there exists at most one $j^{*}$ such that $z^{(j^{*})}_{i}$ lies too close to $B=\{-3/4,-1/2,-1/4,0,1/4,1/2,3/4\}$. Namely, there exists $j^{*}\in[p(N)]$ such that for all $j\in[p(N)]\setminus\{j^{*}\}$, we have $\textup{dist}(z^{(j)}_{i},B)\geq 8g(\varepsilon)$. By 2 it follows that the bit extraction phase in dimension $i$ fails in at most one circuit-simulator.

We thus obtain that the bit extraction (in any dimension) fails in at most $n$ circuit-simulators. Let $X\subseteq[p(N)]$ be such that the bit extraction does not fail in $C_{j}$ for all $j\in X$. Then, we have shown that $|X|\geq p(N)-N\geq p(N)-2N$. By 3, we get that for all $j\in X$, phase 3 of the circuit-simulator $C_{j}$ outputs $\overline{\lambda}(z^{(j)})$, i.e., the correct label for $z^{(j)}$ (which lies in $(\setminus B)^{N}$).

By 4, we have that for every $j\in X$ the circuit-simulator $C_{j}$ outputs