The Complexity of Splitting Necklaces and Bisecting Ham Sandwiches

Computational complexity; Tucker’s Lemma; TFNP; fair division

Introduction

The complexity classes PPA and PPAD were introduced in a seminal paper of Papadimitriou in 1994, in an attempt to classify several natural problems in the class TFNP . TFNP is the class of total search problems in NP for which a solution exists for every instance, and solutions can be efficiently verified. Various important problems were subsequently proven to be complete for the class PPAD, such as the complexity of many versions of Nash equilibrium , market equilibrium computation , and others . As evidence of computational hardness, PPA-completeness is stronger than PPAD-completeness, i.e., $\mbox{{PPAD}}\subseteq\mbox{{PPA}}$. Indeed, Jeřábek shows that it indicates cryptographic hardness in a strong sense: gives a randomised reduction from FACTORING to PPA-complete problems. This is not known for PPAD-complete problems. For more details, and the significance of PPA-completeness, we refer the reader to the related discussion in . PPA is the class of problems reducible to Leaf (Definition 1), and a PPA-complete problem is polynomial-time equivalent to Leaf.

An instance of the problem Leaf consists of an undirected graph $G$ whose vertices have degree at most 2; $G$ has $2^{n}$ vertices represented by bitstrings of length $n$; $G$ is presented concisely via a circuit that takes as input a vertex and outputs its neighbour(s). We stipulate that vertex $0^{n}$ has degree 1. The challenge is to find some other vertex having degree 1.

Complete problems for the class PPA seemed to be much more elusive than PPAD-complete ones, especially when one is interested in “natural” problems, where “natural” here has the very specific meaning of problems that do not explicitly contain a circuit in their definition. Besides Papadimitriou , other papers asking about the possible existence of natural PPA-complete problems include . In a recent precursor to the present paper we identified the first example of such a problem, namely the approximate Consensus-halving problem, dispelling the suspicion that such problems might not exist. In this paper we build on that result and settle the complexity of two natural and important problems whose complexity status were raised explicitly as open problems in Papadimitriou’s paper itself, and in many other papers beginning in the 1980s. Specifically, we prove that Necklace-splitting (with two thieves, see Definition 2) and Discrete Ham Sandwich are both PPA-complete.

In the $k$-Necklace-splitting problem there is an open necklace with $ka_{i}$ beads of colour $i$, for $1\leq i\leq n$. An “open necklace” means that the beads form a string, not a cycle. The task is to cut the necklace in $(k-1)\cdot n$ places and partition the resulting substrings into $k$ collections, each containing precisely $a_{i}$ beads of colour $i$, $1\leq i\leq n$.

In Definition 2, $k$ is thought of as the number of thieves who desire to split the necklace in such a way that the beads of each colour are equally shared. In this paper, usually we have $k=2$ and we refer to this special case as Necklace-splitting.

In the Discrete Ham Sandwich problem, there are $n$ sets of points in $n$ dimensions having integer coordinates (equivalently one could use rationals). A solution consists of a hyperplane that splits each set of points into subsets of equal size (if any points lie on the plane, we are allowed to place them on either side, or even split them arbitrarily).

In Definition 3, each point set represents an ingredient of the sandwich, which is to be cut by a hyperplane in such a way that all ingredients are equally split.

The necklace-splitting problem was introduced in a 1982 paper of Bhatt and Leiserson (, Section 5), where it arose in the context of VLSI circuit design (the version defined in is the 2-thief case proved PPA-complete in the present paper). In 1985 and 1986, the 2-thief case was shown to have guaranteed solutions (as defined in Definition 2) by Goldberg and West and Alon and West and then in 1987, Alon proved existence of solutions for $k$ thieves as well. Early papers that explicitly raise its complexity-theoretic status as an open problem are Goldberg and West and Alon . Subsequently, the necklace-splitting problem was found to be closely related to “paint-shop scheduling”, a line of work in which several papers such as explicitly mention the question of the computational complexity of necklace-splitting. Meunier notes that the search for a minimum number of cuts admitting a fair division (which may be smaller than the number $(k-1)n$ that is guaranteed to suffice) is NP-hard, even for a subclass of instances of the 2-thief case. (That is a result of Bonsma et al. , for the “paint shop problem with words”, equivalent to 2-thief Necklace-splitting with 2 beads of each colour.)

In , we showed Necklace-splitting to be computationally equivalent to $\varepsilon$-Consensus-halving for inverse-polynomial precision parameter $\varepsilon$, but the PPA-completeness of $\varepsilon$-Consensus-halving was only shown for inverse-exponential $\varepsilon$. established PPAD-hardness of Necklace-splitting, applying the main result of . In this paper, we prove that $\varepsilon$-Consensus-halving is PPA-complete for $\varepsilon$ inversely polynomial, thus obtaining the desired PPA-completeness of Necklace-splitting. While some structural parts of our reduction are extensions of those presented in , obtaining the result for inverse-polynomial precision is much more challenging, as the construction needs to move to a high-dimensional space (rather than the two-dimensional space which is sufficient for the result in ). We highlight the main new techniques that we have developed in this paper in Section 2.1, where we provide an overview of the reduction. Our PPA-completeness result gives a convincing negative answer to Meunier and Neveu’s questions about possible polynomial-time solvability or membership of PPAD for Necklace-splitting; likewise it runs counter to Alon’s cautious optimism at ICM 1990 (, Section 4) that the problem may be solvable in polynomial time.

The Ham Sandwich Theorem is of enduring and widespread interest due to its colourful and intuitive statement, and its relevance and applications in topology, social choice theory, and computational geometry. Roughly, it states that given $d$ measures in Euclidean $d$-space, there exists a hyperplane that cuts them all simultaneously in half. Early work on variants and applications of the theorem focused on non-constructive existence proofs and mostly did not touch on the algorithmics. A 1983 paper by Hill hints at possible interest in the corresponding computational challenge, in the context of a related land division problem. The computational problem (and its complexity) was first properly studied in a line of work in computational geometry beginning in the 1980s, for example . The problem envisages input data consisting of $d$ sets of $n$ points in Euclidean $d$-space, and asks for a hyperplane that splits all point sets in half. (The problem Discrete Ham Sandwich (Definition 3) as named in is essentially this, with $d$ set equal to $n$ to emphasise that we care about the high-dimensional case.) In this work in computational geometry, the emphasis has been on efficient algorithms for small values of $d$; Lo et al. improve the dependence on $d$ but it is still exponential, and the present paper shows for the first time that we should not expect to improve on that exponential dependence. More recently, Grandoni et al. apply the “Generalized Ham Sandwich Theorem” to a problem in multi-objective optimisation and note that a constructive proof would allow a more efficient algorithm to emerge. The only computational hardness result we know of is Knauer et al. who obtain a $W$-hardness result for a constrained version of the problem; points out the importance of the computational complexity of the general problem. The PPA-completeness result of the present paper is the first hardness result of any kind for Discrete Ham Sandwich, and as we noted, is a strong notion of computational hardness. Karpic and Saha showing a form of equivalence between the Ham Sandwich Theorem and Borsuk-Ulam, explicitly mention the possible PPA-completeness of Discrete Ham Sandwich as an “interesting and challenging open problem”.

We prove the PPA-completeness of Discrete Ham Sandwich via a simple reduction from Necklace-splitting. Ours is not the first paper to develop the close relationship between the two problems: Blagojević and Soberón shows a generalisation, where multiple agents may share a “sandwich”, dividing it into convex pieces. Further papers to explicitly point out their computational complexity as open problems include Deng et al. (mentioning that both problems “show promise to be complete for PPA”), Aisenberg et al. , and Belovs et al. .

Further Related Work: The class TFNP was defined in and several of its subclasses were studied over the years, such as PPA, PPAD and PPP , PLS and CLS ; here we focus on the most recent results. As we mentioned earlier, in we identified the first natural complete problem for PPA, the approximate Consensus-halving problem. In a recent paper, Sotiraki et al. identified the first natural problem for the class PPP, the class of problems whose totality is established by an argument based on the pigeonhole principle. For the class CLS, both Daskalakis et al. and Fearnley et al. identified complete problems (two versions of the Contraction Map problem, where a metric or a meta-metric are given as part of the input). In the latter paper, the authors define a new class, namely EOPL (for “End of Potential Line”), and show that it is a subclass of CLS. Furthermore, they show that two well-known problems in CLS, the P-Matrix Linear Complementarity Problem (P-LCP), and finding a fixpoint of a piecewise-linear contraction map (PL-Contraction) belong to the class. The End of Potential Line problem of is closely related to the End of Metered Line of .

Problems and Results

We present and discuss our main results, and in Section 2.1 we give an overview of the proof and new techniques, in particular with respect to the precursors to this paper.

An instance $I_{CH}$ incorporates, for $1\leq i\leq n$, a non-negative measure $\mu_{i}$ of a finite line interval $A=[0,x]$, where each $\mu_{i}$ integrates to 1 and $x>0$ is part of the input. We assume that $\mu_{i}$ are step functions represented in a standard way, in terms of the endpoints of intervals where $\mu_{i}$ is constant, and the value taken in each such interval. We use the bit model (logarithmic cost model) of numbers. $I_{CH}$ specifies a value $\varepsilon\geq 0$ also using the bit model. We regard $\mu_{i}$ as the value function held by agent $i$ for subintervals of $A$.

A solution consists firstly of a set of $n$ cut points in $A$ (also given in the bit model of numbers). These points partition $A$ into (at most) $n+1$ subintervals, and the second element of a solution is that each subinterval is labelled $A_{+}$ or $A_{-}$. This labelling is a correct solution provided that for each $i$, $|\mu_{i}(A_{+})-\mu_{i}(A_{-})|\leq\varepsilon$, i.e. each agent has a value in the range $[\frac{1}{2}-\frac{\varepsilon}{2},\frac{1}{2}+\frac{\varepsilon}{2}]$ for the subintervals labelled $A_{+}$ (hence also values the subintervals labelled $A_{-}$ in that range).

We assume without loss of generality that in a valid solution, labels $A_{+}$ and $A_{-}$ alternate. We also assume that the alternating label sequence begins with label $A_{+}$ on the left-hand side of $A$ (i.e. $A_{+}$ denotes the leftmost label in a Consensus-halving solution).

The Consensus-halving problem of Definition 4 is a computational version of the Hobby-Rice theorem . Most of the present paper is devoted to proving the following theorem.

$\varepsilon$-Consensus-halving is PPA-complete for some inverse-polynomial $\varepsilon$.

As mentioned in the introduction, in it was proven that 2-thief Necklace-splitting and $\varepsilon$-Consensus-halving for $\varepsilon$ inversely-polynomial are computationally equivalent, i.e. they reduce to each other in polynomial time. Therefore, by and the “in PPA” result proven in Section B.1, we immediately get the following corollary.

Necklace-splitting is PPA-complete when there are $k=2$ thieves.

If we knew that $k$-Necklace-splitting belonged to PPA for other values of $k$, we could of course make the blanket statement “Necklace-splitting is PPA-complete”. Alas, the proofs that Necklace-splitting is a total search problem for $k>2$ do not seem to boil down to the parity argument on an undirected graph! That being said, we do manage to establish membership of PPA for $k$ being a power of 2 (essentially an insight of ), see Section B of the Appendix for the details and a related discussion. Of course, the $k=2$ result strongly suggests that $k$-Necklace-splitting is a hard problem for other values of $k$.

As it happens, the PPA-completeness of Discrete Ham Sandwich follows straightforwardly, and we present that next. The basic idea of Theorem 2.3 of embedding the necklace in the moment curve appears already in and , p.48.

Inclusion in PPA is shown in Section B.1 of the Appendix. For PPA-hardness, we reduce from 2-thief Necklace-splitting which is PPA-complete by Theorem 2.2.

The idea is to embed the necklace into the moment curve $\gamma=\{(\alpha,\alpha^{2},\ldots,\alpha^{n}):\alpha\in\}$. Assume all beads lie in the unit interval $$. A bead having colour$i\in[n]$located at$\alpha\in$becomes a point mass of ingredient$i$of the ham sandwich located at$(\alpha,\alpha^{2},\ldots,\alpha^{n})\in\mbox{{IR}}^{n}$. It is known that any hyperplane intersects the moment curve$\gamma$in at most$n$points, (e.g. see , Lemma 5.4.2), therefore a solution to Discrete Ham Sandwich corresponds directly to a solution to Necklace-splitting, where the two thieves splitting the necklace take alternating pieces. (In the$k=2$ case, we may assume without loss of generality that they do in fact take alternating pieces).

A limitation to Theorem 2.3 is that the coordinates may be exponentially large numbers; they could not be written in unary. We leave it as an open problem whether a unary-coordinate version is also PPA-complete. As defined in , Discrete Ham Sandwich stipulated that each of the $n$ sets of points is of size $2n$, whereas Definition 3 allows polynomial-sized sets. We can straightforwardly extend PPA-completeness to the version of by adding “dummy dimensions” whose purpose is to allow larger sets of each ingredient; the new ingredients that are introduced, consist of compact clusters of point masses, each cluster in general position relative to the other clusters and the subspace of dimension $n$ that contains the points of interest.

We use the standard notation $[n]$ to denote the set $\{1,\ldots,n\}$, and we also use $\pm[n]$ to denote $\{1,-1,2,-2,\ldots,n,-n\}$. We often refer to elements of $\pm[n]$ as “labels” or “colours”. $\lambda$ is usually used to denote a labelling function (so its codomain is $\pm[n]$).

We let $A$ denote the domain of an instance of Consensus-halving; if that instance has complexity $n$ then $A$ will be the interval $[0,poly(n)]$, where $poly(n)$ is some number bounded by a polynomial in $n$. Recall by Definition 4 that $\mu_{a}$ denotes the value function, or measure, of agent $a$ on the domain $A$, in a Consensus-halving instance. We also associate each agent with its own cut (recall that the number of agents and cuts is supposed to be equal) and we let $c(a)$ denote the cut associated with agent $a$.

We let $p^{C}(n)$ be a polynomial that represents the number of “circuit-encoders” that we use in our reduction (see Section 5.1); we usually denote it $p^{C}$, dropping the $n$ from the notation.

Finally, $B$ denotes the $n$-cube (or “box”) $^{n}$.

In an instance of Consensus-halving, a value-block of an agent $a$ denotes a sub-interval of the domain where $a$ possesses positive value, uniformly distributed on that interval. In our construction, value-blocks tend to be scattered rather sparsely along the domain.

1 Overview of the proof

We review the ground covered by the precursors to this paper, then we give an overview of the technical innovations of the present paper.

established PPAD-hardness of Consensus-halving. An arithmetic circuit can be encoded by an instance to $\varepsilon$-Consensus-halving, by letting each gate have a cut whose location (in a solution) represents the (approximate) value taken at that gate. Agents’ valuation functions ensure that values taken at the gates behave according to the type of gate. A “PPAD circuit” can then be represented using an instance of Consensus-halving.

noted that the search space of solutions to instances as constructed by , is oriented. A radical new idea was needed to encode the non-oriented feature of topological spaces representable by PPA. That was achieved by using two cuts to represent the coordinates of a point on a triangular region faving two sides identified to form a Möbius strip. (These cuts are the only ones that lie in a specific subinterval of the interval $A$ of a Consensus-halving instance, called the “coordinate-encoding (c-e) region”. The two cuts are called the “coordinate-encoding cuts”.) Identifying two sides in this way is done by exploiting the equivalence of taking a cut on the LHS of the c-e region, and moving it to the RHS. In order to embed a hard search problem into the surface of a standard 2-dimensional Möbius strip, it was necessary to work at exponentially-fine resolution, which immediately required inverse-exponential $\varepsilon$ for instances of $\varepsilon$-Consensus-halving. In we reduced from the PPA-complete problem 2D-Tucker (Definition 5 below), a search problem on an exponential-sized 2-dimensional grid.

In , the rest of $A$ is called the “circuit-encoding region” $R$, and the cuts occurring within $R$ do the job of performing computation on the location of cuts in the c-e region. The present paper retains this high-level structure (Section 4.1). As in we use multiple copies of the circuit that performs the computation, each in its own subregion of $R$. Here we use $p^{C}(n)$ copies where $p^{C}$ is a polynomial; in we used 100 copies. Each copy is called a circuit-encoder. The purpose of multiple copies is to make the system robust; a small fraction of copies may be unreliable: as in we have to account for the possibility that one of the c-e cuts may occur in the circuit-encoding region, rendering one of the copies unreliable. We re-use the “double negative lemma” of that such a cut is not too harmful. We also adapt a result of that when a cut is moved from the one end to the other end of the c-e region, this corresponds to identifying two facets of a simplex to form a Möbius strip.

uses a sequence of “sensor agents” to identify the endpoints of intervals labelled $A_{+}$ and $A_{-}$ in the coordinate-encoding region, and feed this information into the above mentioned circuit-encoders, which perform computation on those values. As in we use sensor agents. We obtain a simplification with respect to which is that we do not need the gadgets used there to perform “bit-extraction” (converting the position of a c-e cut into $n$ boolean values). In , a solution to an instance of Consensus-halving was associated with a sequence of 100 points in the Möbius-simplex (referred there as the “simplex-domain”), and the “averaging manoeuvre” introduced in was applied. In this paper, for a polynomial $p^{C}(n)$, we sample a sequence of $p^{C}$ points in a more elegant manner, again exploiting the inverse-polynomial precision of solutions that we care about.

1.2 Technical innovations

As in , we reduce from the PPA-complete problem 2D-Tucker (Definition 5). That computational problem uses an exponentially-fine 2D grid, and (unlike ), in Section 3 we apply the snake-embedding technique invented in (versions of which are used in in the context of PPA) to convert this to a grid of fixed resolution, at the expense of going from 2 to $n$ dimensions. The new problem, Variant high-D Tucker (Definition 7) envisages a $7\times 7\times\cdots\times 7$ grid. Here, we design the snake-embedding in such a way that PPA-completeness holds for instances of the high-dimensional problem that obey a further constraint on the way the high-dimensional grid is coloured, that we exploit subsequently. A further variant, New variant high-D Tucker (Definition 8) switches to a “dual” version where a hypercube is divided into cubelets, and points in the hypercube are coloured such that interiors of cubelets are monochromatic. A pair of points is sought having equal and opposite colours and distant by much less than the size of the cubelets.

We encode a point in $n$ dimensions using a solution to an instance of Consensus-halving as follows. Instead of having just 2 cuts in the coordinate-encoding region (as in ), suppose we ensure that up to $n$ cuts lie there. These cuts split this interval into $n+1$ pieces whose total length is constant, so represent a point in the unit $n$-simplex (in , the unit 2-simplex). This “Möbius-simplex” (Definition 17; Figure 10) has the further property that two facets are identified with each other in a way that effectively turns the simplex into an $n$-dimensional Möbius strip.

In Section 5.2 we define a crucially-important coordinate transformation (see Figure 11) with the following key properties

the transformation and its inverse can be computed efficiently, and distances between transformed coordinate vectors are polynomially related to distances between un-transformed vectors;

at the two facets that are identified with each other, the coordinates of corresponding points are the negations of each other; our colouring function (that respects Tucker-style boundary conditions) has the effect that antipodal points get equal and opposite colours, and no undesired solutions are introduced at these facets.

This is the “smooth embedding” referred to in the abstract.

With the aid of the above coordinate transformation, we divide up the Möbius-simplex:

The twisted tunnel (Definition 23) is an inverse-polynomially thick strip, connecting the two facets that are identified in forming the Möbius-simplex. It contains at its centre an embedded copy of the hypercube domain of an instance $I_{VT}$ of New variant high-D Tucker. Outside of this embedded copy, it is “coloured in” (using our new coordinate system) in a way that avoids introducing solutions that do not encode solutions of $I_{VT}$.

The Significant Region contains the twisted tunnel and constitutes a somewhat thicker strip connecting the two facets. It serves as a buffer zone between the twisted tunnel and the rest of the Möbius-simplex. It is subdivided into subregions where each subregion has a unique set of labels, or colours, from $\pm[n]$. (We sometimes refer to these as “colour-regions”.) It is shown that any solution to an instance of Consensus-halving constructed as in our reduction, represents a point in the Significant Region.

If, alternatively, a set of cuts represents a point from outside the Significant Region, then certain agents (so-called “blanket-sensor agents”) will observe severe imbalances between labels $A_{+}$ and $A_{-}$, precluding a solution.

In , it was relatively straightforward to integrate the subset of the 2-dimensional Möbius-simplex that corresponds with the twisted tunnel, with the parts of the domain where the blanket-sensor agent became active (ruling out a solution) in a way that avoided introducing solutions that fail to encode solutions of Tucker. In the present paper, that gap has to be “coloured-in” in a carefully-designed way (Section 5.3, list item 3), and this is the role of the part of the Significant Region that is not the twisted tunnel. The proofs that they work correctly (Sections 6.2, 6.3) become more complicated.

Snake embedding reduction

The purpose of this section is to establish the PPA-completeness of New variant high-D Tucker, Definition 8. The snake embedding construction was devised in , in order to prove that $\varepsilon$-Nash equilibria are PPAD-complete to find when $\varepsilon$ is inverse polynomial; without this trick the result is just obtained for $\varepsilon$ being inverse exponential. We do a similar trick here. We will use as a starting-point the PPA-completeness of 2D-Tucker, from , which is the following problem:

(Aisenberg et al. ) An instance of 2D-Tucker consists of a labelling $\lambda:[m]\times[m]\rightarrow\{\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 of 2D-Tucker 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 hardness of the problem in Definition 5 arises when $m$ is exponentially-large, and the labelling function is presented by means of a boolean circuit.

We aim to prove the following is PPA-complete, even when the values $m_{i}$ are all upper-bounded by some constant (specifically, 7).

(Aisenberg et al. ) An instance of $n$D-Tucker consists of a labelling $\lambda:[m_{1}]\times\cdots\times[m_{n}]\rightarrow\{\pm 1,\cdots,\pm n\}$ such that if a point ${\bf x}=(x_{1},\ldots,x_{n})$ lies on the boundary of this grid (i.e., $x_{i}=1$ or $x_{i}=m_{i}$ for some $i$), then letting $\bar{\bf x}$ be the antipodal point of x, we have $\lambda(\bar{\bf x})=-\lambda({\bf x})$. (Two boundary points are antipodal if they lie at opposite ends of a line segment passing through the centre of the grid.) A solution consists of two points z, ${\bf z}^{\prime}$ on this grid, having opposite labels ($\lambda({\bf z})=-\lambda({\bf z}^{\prime})$), each of whose coordinates differ (coordinate-wise) by at most 1.

It is assumed that $\lambda$ is presented in the form of a circuit, syntactically constrained to give opposite labels to antipodal grid points.

An instance of Variant high-D Tucker is similar to Definition 6 but whose instances obey the following additional constraints. The $m_{i}$ are upper bounded by the constant 7. We impose the further constraint that the facets of the cube are coloured with labels from $\pm[n]$ such that all colours are used, and opposite facets have opposite labels, and for $2\leq i\leq n$ it holds that the facet with label $i$ (resp. $-i$) has no grid-point on that facet with label $i$ (resp. $-i$).

A snake-embedding consists of a reduction from $k$D-Tucker to $(k+1)$D-Tucker, which we describe informally as follows. See Figure 1. Let $I$ be an instance of $k$D-Tucker, on the grid $[m_{1}]\times\cdots\times[m_{k}]$. Embed $I$ in $(k+1)$-dimensional space, so that it lies in the grid $[m_{1}]\times\cdots\times[m_{k}]\times$. Then sandwich $I$ between two layers, where all points in the top layer get labelled $k+1$, and points in the bottom layer get labelled $-(k+1)$, as in the left part of Figure 1. We now have points in the grid $[m_{1}]\times\cdots\times[m_{k}]\times$, and notice that this construction preserves the required property that points on the boundary have labels opposite to their antipodal points.

Then, the main idea of the snake embedding is the following. We fold this grid into three layers, by analogy with folding a sheet of paper along two parallel lines so that the cross-section is a zigzag line, and one dimension of the folded paper is one-third of the unfolded version, the other dimension being unchanged (see the right hand side of Figure 1). In higher dimension, suppose that $m_{1}$ is the largest value of any $m_{i}$. Then, we can reduce $m_{1}$ by a factor of about 3, while causing the final coordinate to go up from 3 to 9. By merging layers of label $k+1$ and $-(k+1)$, the thickness of 9 reduces to 7. This operation preserves the labelling rule for antipodal boundary points.

However, there are two points that need extra care for the reduction to go through:

Firstly, simply folding the layers such that their cross-sections are zigzag lines may introduce diagonal adjacencies between cubelets that were not present in the original instance in $k$-dimensions, i.e. we might end up generating adjacent cubelets with equal-and-opposite colours, see the left part of Figure 2 for an illustration. To remedy this, we will “copy” (or “duplicate”) the cubelets at the folding points, essentially having three cubelets of the same colour, whose cross-sections are the short vertical section in the right hand side of Figure 1, see also the right hand side of Figure 2 for an illustration. From now on, when referring to “folding”, we will mean the version where we also duplicate the cubelets at the folding points, as described above.

Secondly, the folding and duplicating operation only works if $m_{1}$ is a multiple of $3$, as otherwise the $(k+1)$-dimensional instance may not satisfy the boundary conditions of Definition 6, i.e. we might end up with antipodal cubelets that do not have equal-and-opposite colours. To ensure that $m_{1}$ is a multiple of $3$ before folding, we can add $1$ or $2$ additional layers of cubelets to $m_{1}$, (depending on whether the remainder of the division of $m_{1}$ by $3$ is either $2$ or $1$ respectively). These layers are duplicate copies of the outer layers of cubelets at opposite ends of the length-$m_{1}$ direction; if there is only one additional layer to be added, we can add on either side. Note that this operation does not generate any cubelets of equal-and-opposite labels that were not there before and the same will be true for the instance after the folding operation. See Figure 3 for an illustration.

Let $I$ be an instance of $k$D-Tucker having coordinates in ranges $[m_{1}],\ldots,[m_{k}]$ and label function $\lambda$. Select the largest $m_{i}$, breaking ties lexicographically. Assume for simplicity in what follows that $m_{1}$ is largest.

if $x_{1}^{\prime}\leq m_{1}$, ${\bf x}^{\prime}$ is mapped to ${\bf x}=(x_{1}^{\prime},\ldots,x_{k}^{\prime})$ and $\lambda^{\prime}({\bf x}^{\prime})=\lambda({\bf x})$.

if $x_{1}^{\prime}=m_{1}+1$, ${\bf x}^{\prime}$ is mapped to ${\bf x}=(m_{1},\ldots,x_{k}^{\prime})$ and $\lambda^{\prime}({\bf x}^{\prime})=\lambda({\bf x})$.

In other words, points for which the first coordinate ranges from $1$ to $x_{1}^{\prime}$, are mapped to themselves and receive their own label, and points for which the first coordinate is $m_{1}+1$ are mapped to the points where the first coordinate is $m_{1}$, receiving the label of that point. This essentially “duplicates” the layer of cubelets on the right endpoint of the $m_{1}$-direction. See Figure 3 for an illustration.

if $x_{1}^{\prime}=1$, ${\bf x}^{\prime}$ is mapped to ${\bf x}=(1,\ldots,x_{k}^{\prime})$ and $\lambda^{\prime}({\bf x}^{\prime})=\lambda({\bf x})$.

if $2\leq x_{1}^{\prime}\leq m_{1}+1$, ${\bf x}^{\prime}$ is mapped to ${\bf x}=(x_{1}^{\prime}-1,\ldots,x_{k}^{\prime})$ and $\lambda^{\prime}({\bf x}^{\prime})=\lambda({\bf x})$. This is similar to the mapping and labelling in the previous case, except for the fact that we need to “shift” the labels of the points, since we essentially introduced a copy of the layer of cubelets on the left endpoint of the $m_{1}$-direction. See Figure 3 for an illustration.

From $k$ to $k+1$ dimensions. Starting from an instance $I$ of $kD$-Tucker, we will construct an instance $I^{\prime}$ of $(k+1)D-$Tucker as follows. Let ${\bf x}=(x_{1},\ldots,x_{k})$ be a point in $[m_{1}]\times\ldots\times[m_{k}]$ with labelling function $\lambda$. We will associate each such point with a corresponding point ${\bf x}^{\prime}$ in $\left[\frac{m_{1}}{3}+2\right]\times\ldots\times[m_{k}]\times$ and a label $\lambda^{\prime}({\bf x}^{\prime})$ as follows.

If $x_{1}\leq\frac{m_{1}}{3}$, then ${\bf x}$ is mapped to ${\bf x}^{\prime}=(x_{1},\ldots,x_{k},2)$, and $\lambda^{\prime}({\bf x}^{\prime})=\lambda({\bf x})$.

If $x_{1}=\frac{m_{1}}{3}+1$ (the first “folding” point), then ${\bf x}$ is mapped to the following three points in $I^{\prime}$ and receives the following colours (see the shaded cubelets at the right-hand side of Figure 2):

${\bf x}^{\prime}=(\frac{m_{1}}{3}+1,\ldots,x_{k},2)$ (the original cubelet) and $\lambda^{\prime}({\bf x}^{\prime})=\lambda({\bf x})$.

${\bf x}^{\prime}=(\frac{m_{1}}{3}+1,\ldots,x_{k},3)$ (the first copy) and $\lambda^{\prime}({\bf x}^{\prime})=\lambda({\bf x})$.

${\bf x}^{\prime}=(\frac{m_{1}}{3}+1,\ldots,x_{k},4)$ (the second copy) and $\lambda^{\prime}({\bf x}^{\prime})=\lambda({\bf x})$.

If $\frac{m_{1}}{3}+2\leq x_{1}\leq\frac{2m_{1}}{3}-1$, then x is mapped to ${\bf x}^{\prime}=(\frac{2m_{1}}{3}+2-x_{1},x_{2},\ldots,x_{k},4)$, with $\lambda^{\prime}({\bf x}^{\prime})=\lambda({\bf x})$.

If $x_{1}=\frac{2m_{1}}{3}$ (the second “folding” point), then ${\bf x}$ is mapped to the following three points in $I^{\prime}$ and receives the following colours:

${\bf x}^{\prime}=(2,\ldots,x_{k},4)$ (the original cubelet) and $\lambda^{\prime}({\bf x}^{\prime})=\lambda({\bf x})$.

${\bf x}^{\prime}=(2,\ldots,x_{k},5)$ (the first copy) and $\lambda^{\prime}({\bf x}^{\prime})=\lambda({\bf x})$.

${\bf x}^{\prime}=(2,\ldots,x_{k},6)$ (the second copy) and $\lambda^{\prime}({\bf x}^{\prime})=\lambda({\bf x})$.

If $\frac{2m_{1}}{3}+1\leq x_{1}\leq m_{1}$, then ${\bf x}$ is mapped to ${\bf x}^{\prime}=(x_{1}+2-\frac{2m_{1}}{3},x_{2},\ldots,x_{k},6)$, with $\lambda^{\prime}({\bf x}^{\prime})=\lambda({\bf x})$.

Set $\lambda^{\prime}(1,\ldots,1)=-k$, along with any point x connected to it via a path of points that have not been labelled by the above procedure.

Set $\lambda^{\prime}(\frac{m_{1}}{3}+2,m_{2},\ldots,m_{k},7)=k$, along with any point x connected to it via a path of points that have not been labelled by the above procedure.

First, it is not hard to check that the the composition of $O(n)$ snake-embeddings is a polynomial-time reduction. Also note that, by the way the high-dimensional instances is constructed, we have not introduced any adjacencies that did not already exist, i.e. if there is a pair of adjacent cubelets with equal-and-opposite labels in the instance $I^{\prime}$ of the high-dimensional version, this pair is present in the instance $I$ of the $2D$ version as well, and it is easy to recover it in polynomial time. Therefore, it suffices to show how to obey the additional constraint of Variant high-D Tucker, namely that for $i\geq 2$, a side having label $i$ has no grid-points with label $i$, and similarly for $-i$.

We begin as in (see Figure 1 in that paper), by taking the original $2D$ instance $I$, of size $m\times m$, and extend to an instance of size $3m\times m$ as follows. The original instance is embedded in the centre of the new instance. Each region $R$ to the sides (of size $m\times m$) are labelled by copying the edge of $I$ facing $R$, along an adjacent edge of $R$, and connecting these two edges with paths that have two straight sections and connect 2 points of the same label, and points along that path have that label. The outermost path then labels a side of the new instance of length $m$, so these two opposite sides get opposite labels. We may assume (by switching $1$’s and $2$’s if needed) that these new opposite sides are labelled $\pm 2$.

The $S$-fold approach shown in Figure 1 (in this paper) can be checked to retain this property. When we sandwich a cuboid between two layers of opposite (new) colours (call them $c$ and $-c$), as shown in Figure 1, we label the new facets thus formed with $-c$ and $c$ respectively. We label the other facets with their original labels (each of these facets has acquired the labels $c$ and $-c$, and no other labels). The folding operation has a natural correspondence between the facets of the unfolded and folded versions of the cuboid. It can be checked that the set of colours of a facet before folding is the same as the set of colours of the corresponding facets after folding.

It is convenient to define the following problem, whose PPA-completeness follows fairly directly from the PPA-completeness of Variant high-D Tucker.

An instance of New variant high-D Tucker in $n$ dimensions is presented by a boolean circuit $C_{VT}$ that takes as input coordinates of a point in the hypercube $B=^{n}$ and outputs a label in $\pm[n]$ (assume $C_{VT}$ has $2n$ output gates, one for each label, and is syntactically constrained such that exactly one output gate will evaluate to true), having the following constraints that may be enforced syntactically.

Dividing $B$ into $7^{n}$ cubelets of edge length $2/7$ using axis-aligned hyperplanes, all points in the same cubelet get the same label by $C_{VT}$;

Interiors of antipodal boundary cubelets get opposite labels;

Points on the boundary of two or more cubelets get a label belonging to one of the adjacent cubelets;

Facets of $B$ are coloured with labels from $\pm[n]$ such that all colours are used, and opposite facets have opposite labels. For $2\leq i\leq n$ it also holds that the facet with label $i$ (resp. $-i$) does not intersect any cubelet having label $i$ (resp. $-i$). Facets coloured $\pm 1$ are unrestricted (we call them the “panchromatic facets”).

A solution consists of a polynomial number $p^{C}$ of points that all lie within an inverse polynomial distance $\delta(n)$ of each other (for concreteness, assume $\delta(n)=1/100n$). At least two of those points should receive equal and opposite labels by $C_{VT}$.

New variant high-D Tucker corresponds to the problem Variant Tucker in ; in that paper a solution only contained 100 points, while here we use $p^{C}$ points. Here we need more points since we are in $n$ dimensions, and our analysis needs to tolerate $n$ points receiving unreliable labels.

Some building-blocks and definitions

Here we set up some of the general structure of instances of Consensus-halving constructed in our reduction. We identify some basic properties of solutions to these instances. We define the Möbius-simplex and the manner in which a solution encodes a point on the Möbius-simplex. The encoding of the circuitry is covered in Section 5.

We use the following values throughout the paper.

$\delta^{\rm tiny}$ is an inverse-polynomial quantity in $n$, chosen to be substantially smaller than any other inverse-polynomial quantity that we use in the reduction, apart from $\varepsilon$ (below).

$\delta^{T}$ is an inverse-polynomial quantity in $n$, which is smaller than any other inverse-polynomial quantity apart from $\delta^{\rm tiny}$ and is larger than $\delta^{\rm tiny}$ by an inverse-polynomial amount. The quantity $\delta^{T}$ denotes the width of the so-called “twisted tunnel” (see Definition 23).

$p^{\rm huge}$ denotes a large polynomial in $n$; specifically we let $p^{\rm huge}=n/\delta^{\rm tiny}$. The quantity $p^{\rm huge}$ represents the number of sensor agents for each circuit encoder (see Definition 13).

$p^{\rm large}$ denotes a large polynomial in $n$, which is however smaller than $p^{\rm huge}$ by a polynomial factor. The quantity $p^{\rm large}$ will be used in the definition of the “blanket-sensor agents” (see Definition 14) and will quantify the extent to which the cuts in the “coordinate-encoding region” (Definition 9) are allowed to differ from being evenly spaced, before the blanket-sensor agents become active (see Section 4). The choice of $p^{\rm large}$ controls the value $\delta_{w}$ of the radius of the Significant Region (see Proposition 4.4), with larger $p^{\rm large}$ meaning larger $\delta_{w}$.

$\varepsilon$ is the precision parameter in the Consensus-Halving solution, i.e. each agent $i$ is satisfied with a partition as long as $|\mu_{i}(A_{+})-\mu_{i}(A_{-})|\leq\varepsilon$. Henceforth, we will set $\varepsilon=\delta^{\rm tiny}/10$.

1 Basic building-blocks

We consider instances $I_{CH}$ of Consensus-halving that have been derived from instances $I_{VT}$ of New variant high-D Tucker in $n$ dimensions. The general aim is to get any solution of such an instance $I_{CH}$ to encode a point in $n$ dimensions that “localises” a solution to $I_{VT}$, by which we mean that from the solution of $I_{CH}$, we will be able to find a point on the $I_{VT}$ instance that can be transformed to a solution of $I_{VT}$ in polynomial time and fairly straightforwardly.

Coordinate-encoding region (c-e region) Given an instance of Variant high-D Tucker in $n$ dimensions, the corresponding instance of Consensus-halving has a coordinate-encoding region, the interval $[0,n]$, a (prefix) subinterval of $A$.

The valuation functions of agents in an instance $I_{CH}$ of Consensus-halving obtained by our reduction from an instance of New variant high-D Tucker in $n$ dimensions, will be designed in such a way that either $n-1$ or $n$ cuts (typically $n$) must occur in the coordinate-encoding region, in any solution. Furthermore, the distance between consecutive cuts must be close to 1 (an additive difference from 1 that is upper-bounded by an inverse polynomial), shown in Proposition 4.4.

Coordinate-encoding agents (c-e agents). Given an instance of New variant high-D Tucker in $n$ dimensions, the corresponding instance of Consensus-halving has $n$ coordinate-encoding agents denoted $\{a_{1},\ldots,a_{n}\}$.

The $n$ c-e agents have associated $n$ coordinate-encoding cuts (Definition 11). It will be seen that the c-e cuts typically occur in the c-e region. The c-e agents do not have any value for the coordinate-encoding region; their value functions are only ever positive elsewhere. In particular, they have blocks of value whose labels $A_{+}/A_{-}$ are affected by the output gates of the circuitry that is encoded to the right of the c-e region.

Coordinate-encoding cuts (c-e cuts). We identify $n$ cuts as the coordinate-encoding cuts. In the instances of Consensus-halving that we construct, in any (sufficiently good approximate) solution to the Consensus-halving instance, all other cuts will be constrained to lie outside the c-e region (and it will be straightforward to see that the value functions of their associated agents impose this constraint). A c-e cut is not straightforwardly constrained to lie in the c-e region, but it will ultimately be proved that in any approximate solution, the c-e cuts do in fact lie in the c-e region.

Recall that $p^{\rm huge}=n/\delta^{\rm tiny}$ from Section 2, which implies that the c-e region can be divided into $p^{\rm huge}$ intervals of length $\delta^{\rm tiny}$ (see also Figure 4).

$\sigma$-shifted version. Given a value function $f$ (or measure) on the c-e region $[0,n]$, we say that another function $f^{\prime}$ on the c-e region is a $\sigma$-shifted version of $f$, when we have that $f^{\prime}((x-\sigma)\mod n)=f(x)$.

Recall that the circuit-encoding region (details in Section 5) contains $p^{C}$ circuit-encoders, mentioned in the following definitions.

Sensor agents. Each circuit-encoder $C_{i}$, $i=1,\ldots,p^{C}$, has a set ${\cal S}_{i}$ of sensor agents. ${\cal S}_{i}=\{s_{i,1},\ldots,s_{i,p^{\rm huge}}\}$ where the $s_{i,j}$ are defined as follows. When $i=1$, $s_{1,j}$ has value $\frac{1}{10}$ uniformly distributed over the interval

For $i>1$, $s_{i,j}$ is a $\frac{1}{p^{C}}(i-1)\delta^{\rm tiny}$-shifted version of $s_{1,j}$.

Each sensor agent $s_{i,j}$ also has valuation outside the c-e region, in non-overlapping intervals of the circuit-encoding region $R_{i}$ (see Section 5.1). This valuation consists of two valuation blocks of value $\frac{9}{20}$ each, with no other valuation block in between. These are exactly as described in , see also Appendix A and Figure 16 for an illustration.

This value gadget for $s_{i,j}$ causes the $j$-th input gate in the circuit-encoder $C_{i}$ to be set according to the label received by $s_{i}$’s block of value in the c-e region, i.e. jump to the left or to the right in order to indicate that the corresponding value-block of $s_{i}$ in the c-e region is labelled $A_{+}$ or $A_{-}$.

According to the definitions above, $C_{1}$ has a sequence of (a large polynomial number of) sensor agents that have blocks of value in a sequence of small intervals going from left to right of the c-e region (see Figure 4). For $1<i\leq p^{C}$, $C_{i}$ has a similar sequence, shifted slightly to the right on the c-e region (by $\delta^{\rm tiny}(i-1)/p^{C}$). For $j\in[p^{\rm huge}]$, the intervals defined by the value-blocks of the sensor agents $s_{1,j},\ldots,s_{p^{C},j}$ (for $C_{1},\ldots,C_{p^{C}}$) partition the interval $[(j-1)\delta^{\rm tiny},j\delta^{\rm tiny}]$.

Remark: Note that a c-e cut may divide one of the above value-blocks held by a sensor agent in the c-e region, and in that case the input being supplied (using the gadget of ) to its circuit-encoder is unreliable. However, only $n$ sensor agents may be affected in that way, and their circuit-encoders will get “out-voted” by the ones that receive valid boolean inputs. This is part of the reason why we use $p^{C}$ circuit-encoders in total. More details on this averaging argument are provided in Section 5.

Blanket-sensor agents. Each circuit-encoder $C_{i}$ shall have $n-1$ blanket-sensor agents $b_{i,2},\ldots,b_{i,n}$.

In $C_{1}$, for each $j=2,\ldots,n$, blanket-sensor agent $b_{1,j}$ has value $1/10$ distributed over $[j-2,j]$ (see Figure 4). This value consists of a sequence

of $2/\delta^{\rm tiny}=2p^{\rm huge}/n$ value-blocks, each of length $\delta^{\rm tiny}/p^{C}$ and of value $\frac{1}{10}\cdot(\delta^{\rm tiny}/2)$.

In each $C_{i}$, $1<i\leq p^{C}$, and for each $j=2,\ldots,n$, the value function of $b_{i,j}$ that lies in the c-e region is an $(i-1)\frac{\delta^{\rm tiny}}{p^{C}}$-shifted version of $b_{1,j}$.

The remaining value $9/10$ of each $b_{i,j}$ consists of 3 value-blocks of width $\delta^{\rm tiny}$ lying in a subinterval $I_{i,j}$ of the circuit-encoding region $R_{i}$ (see Section 5.1), such that:

respectively, where \kappa=\Bigl{(}\frac{1}{10}\frac{\delta^{\rm tiny}}{2}\Bigr{)}p^{\rm large}.

$I_{i,j}$ contains also value-blocks of agents for each gate that takes the value of $b_{i,j}$ as input (the feedback gadgetry, see Section 5.1.2).

The value of the blanket-sensor agents in $I_{i,j}$ is very similar to the gadget used in , see Appendix A (of the present paper) and Figure 17. The structure of the blanket-sensor agents in the c-e region is shown in Figure 4.

Each blanket-sensor agent $b_{i,j}$ has an associated cut $c(b_{i,j})$ that lies in the subinterval $I_{i,j}$. Agent $b_{i,j}$ “monitors” an interval of length 2, namely the interval $[j-2,j]$ within which the sequence of $2/\delta^{\rm tiny}$ value-blocks lie. If, in this interval, the number of these value-blocks labelled $A_{+}$ exceeds the number labelled $A_{-}$ by at least $p^{\rm large}$ (recall that $p^{\rm large}$ is a large polynomial which is however polynomially smaller than $p^{\rm huge}$) then (in any $\varepsilon$-approximate solution to $I_{CH}$, where, recall, $\varepsilon=\delta^{\rm tiny}/10$), the cut $c(b_{i,j})$ in $I_{i,j}$ lies in either the right-hand or the left-hand value-block, otherwise it lies in the central value-block. Note that these three possible positions may be converted to boolean values that influence circuit-encoder $C_{i}$; this was referred to as a “bit-detection gadget” in , see Appendix A for more details.

We say that blanket-sensor $b_{i,j}$ is active if $b_{i,j}$ in fact observes a sufficiently large label discrepancy in the c-e region, that $c(b_{i,j})$ lies in one of the two outer positions, left or right, and not in the central position. We say that $b_{i,j}$ is active towards $A_{+}$ if $A_{+}$ is the overrepresented label, with similar terminology for $A_{-}$.

When blanket-sensor agent $b_{i,j}$ is active, it provides input to $C_{i}$ that causes $C_{i}$ to label the value held by $a_{j}$ and controlled by $C_{i}$, to be either $A_{+}$ or $A_{-}$; the choice depends on the over-represented label in $[j-2,j]$ and the parity of the index of the blanket-sensor agent. The precise feedback mechanism to the c-e agent $a_{j}$ by the blanket-sensor $b_{i,j}$ is described in Section 5.1.3.

When no blanket-sensors are active, the sequence of c-e cuts encodes a point in the Significant Region (Definition 18).

In , we worked just in two dimensions and there was just one blanket-sensor agent for the entire c-e region, for each circuit-encoder. Note also that there, the blanket-sensor agent had a single value-block of length 2; here we split it into a polynomial sequence of small value-blocks. The advantage of using a polynomial sequence of value-blocks (which could not have been done in due to the exponential precision requirement) is that we can argue that in all but at most $n$ circuit-encoders, the blanket-sensor agents have value-blocks that are not cut by the c-e cuts, so we can be precise about how big a disparity between blocks labelled $A_{+}$ and $A_{-}$ cause a blanket-sensor to be active, and for at most $n$ circuit-encoders, we regard them as having unreliable inputs (see Definition 16 and Observation 4.2).

2 Features of solutions

The main result of this section is Proposition 4.4, that in a solution to approximate Consensus-halving as constructed here, the sequence of cuts in the c-e region are “evenly spaced” in the sense that the gap between consecutive cuts differs from 1 by at most an inverse-polynomial.

Given an instance $I_{CH}$ derived by our reduction from an instance of New variant high-D Tucker in $n$ dimensions, any inverse-polynomial approximate solution of $I_{CH}$ has the property that at most $n$ cuts lie in the coordinate-encoding region. This is because all other cuts are associated with agents who have at least $9/10$ of their value strictly to the right of the c-e region, thus in a solution, those cuts cannot lie in the c-e region.

We will say that a circuit-encoder receives reliable input, if no coordinate-encoding cut passes through value-blocks of its sensor agents.

At most $n$ circuit-encoders fail to receive reliable input (by Observation 4.1 and the fact that sensors of distinct circuit-encoders have value in distinct intervals).

When a circuit-encoder receives reliable input, it is straightforward to interpret the labels allocated to its sensors, as boolean values, and simulate a circuit computation on those values, ultimately passing feedback to the c-e agents via value-blocks that get labelled according to the output gates of the circuit being simulated. This is done in a conceptually similar way to that described in (e.g. see Sections 4.4.2 and 4.6 in ), see also Appendix A of the present paper.

The Möbius-simplex. The Möbius-simplex in $n$ dimensions consists of points ${\bf x}$ in $\mbox{{IR}}^{n+1}$ whose coordinates are non-negative and sum to 1. We identify every point $(x_{1},\ldots,x_{n},0)$ with the point $(0,x_{1},\ldots,x_{n})$, for all non-negative $x_{1},\ldots,x_{n}$ summing to 1. We use the following metric $d(\cdot,\cdot)$ on the Möbius-simplex, letting $L_{1}$ be the standard $L_{1}$ distance on vectors:

where $(0,x_{1},\ldots,x_{n})\equiv(x_{1},\ldots,x_{n},0)$.

Let $I_{CH}$ be an instance of Consensus-halving, obtained by reduction from New variant high-D Tucker in $n$ dimensions, hence having c-e region $[0,n]$. Note that, by Observation 4.1, at most $n$ cuts may lie in the c-e region. A set of $k\leq n$ cuts of the coordinate-encoding region splits it into $k+1$ pieces. We associate such a split with a point ${\bf x}$ in $\mbox{{IR}}^{n+1}$ as follows. The first coordinate is the distance from the LHS of the consensus-halving domain to the first cut, divided by $n$, the length of the c-e region. For $2\leq i\leq k+1$, the $i$-th coordinate of ${\bf x}$ is the distance between the $i-1$-st and $i$-th cuts, divided by $n$. Remaining coordinates are 0.

If there are $n-1$ cuts in the c-e region, suppose we add a cut at either the LHS or the RHS. These two alternative choices correspond to a pair of points that have been identified as the same point, as described in Definition 17. (Observation 5.3 makes a similar point regarding transformed coordinates.)

Each circuit-encoder reads in “input” representing a point in the Möbius-simplex. Any circuit-encoder $C_{i}$ ($i\in[p^{C}]$) behaves like $C_{1}$ on a point ${\bf x}_{i}$, for which (for all $i,j\in[p^{C}]$) $d({\bf x}_{i},{\bf x}_{j})\leq\delta^{\rm tiny}$ (recall $d$ is defined in (1)). Consequently their collective output (the split between $A_{+}$ and $A_{-}$ of the value held by the c-e agents) is the output of a single circuit-encoder averaged over a collection of $p^{C}$ points in the Möbius-simplex, all within $\delta^{\rm tiny}$ of each other.

This follows by inspection of the way the $p^{C}$ circuit-encoders differ from each other: their sensor-agents are shifted but their internal circuitry is the same.

The Significant Region of the Möbius-simplex $D$. The Significant Region of $D$ consists of all points in $D$ where no blanket-sensors are active (where “blanket-sensors” and “active” are defined in Definition 15).

There is an inverse-polynomial value $\delta^{w}$ such that all points ${\bf x}=(x_{1},\ldots,x_{n+1})$ in the Significant Region have coordinates $x_{i}$ that for $2\leq i\leq n$ differ from $1/n$ by at most $\delta^{w}$, if ${\bf x}$ is encoded by the c-e cuts of an $\varepsilon$-approximate solution to one of our instances of Consensus-halving. (Recall that $\varepsilon=\delta^{\rm tiny}/10$).

Thus, if an instance $I_{CH}$ of Consensus-halving (obtained using our reduction) has a solution $S_{CH}$, then all the c-e cuts in $S_{CH}$ have the property that the distance between two consecutive c-e cuts differs from 1 by at most some inverse-polynomial amount.

Before we proceed with the proof of the proposition, we will state a few simple lemmas that will be used throughout the proof. We start with the following definition.

Intuitively, cuts that are $\delta$-close to integer points lie close (within distance at most $\delta$) to either the endpoints or the midpoint of some monitored interval $[j-2,j]$.

An interval $I$ is a monochromatic interval if it is not intersected by any cuts (which means that it receives a single label). Additionally, if for $A_{j}\in\{A_{+},A_{-}\}$, $I$ is labelled with $A_{j}$, then we will say that $I$ is a monochromatic interval of label $A_{j}$.

It should be clear that if any monitored interval $[j-2,j]$ has a large enough (larger than $1+\delta$) monochromatic subinterval, then the blanket-sensor agent $b_{1,j}$ is active.

In $I$, there are at least $k-1$ intervals monitored by blanket-sensor agents and we only have at most $k-2$ cuts at our disposal. With $k-2$ cuts, we can partition an interval of length $k$ in at most $k-1$ intervals, the largest of which, call it $I_{\text{max}}$, will have length at least $1+1/k$. Since $\delta<1/2n$, the length of $I_{max}$ is actually larger than $1+\delta$. The lemma follows then from the fact that, since the monitored intervals partition the interval $I$, $I_{max}$ will contain a monochromatic interval of length at least $1+\delta$, which will be entirely contained in some monitored interval, and the corresponding blanket-sensor agent will be active.

each of the $k-1$ cuts in $I$ will be $\delta$-close to a different integer point and these integer points will be the midpoints of the monitored subintervals contained entirely in $I$ or

at least one of the blanket-sensors monitoring the subintervals in $I$ will be active.

In $I$, there are at least $k-1$ intervals monitored by blanket-sensor agents and we have $k-1$ cuts at our disposal. Assume that there exists some integer point $j-1$ which is a midpoint of some monitored interval $[j-2,j]\subseteq I$ such that there exists no cut that is $\delta$-close to $j-1$. This implies that either $[j-2,j]$ is intersected by at least $2$ cuts, or the blanket-sensor agent corresponding to $[j-2,j]$ will be active. To see this, note that if there were not any cuts in $[j-2,j]$ then obviously the whole interval $[j-2,j]$ would be monochromatic and the corresponding blanket-sensor would be active. If $[j-2,j]$ was intersected by a single cut, since the cut lies at distance at least $\delta$ from the midpoint of the interval, there would exist a monochromatic subinterval of $[j-2,j]$ of length at least $1+\delta$, activating the corresponding blanket-sensor agent $b_{1,j}$.

However, for the blanket-sensor agent $b_{1,j}$ to not be active, it would have to be the case that some other cut in the interval $[j-2,j]$ is also not $\delta$-close to the midpoint of one of the adjacent monitored intervals, therefore generating an imbalance in labels that has to be compensated with at least one additional cut in that interval. Given that there are only $k-1$ cuts in the interval $I$, it follows that in some monitored subinterval $[j^{\prime},j^{\prime}-2]$ there will be a large enough imbalance, i.e a monochromatic subinterval of length at least $1+\delta$, and the corresponding blanket-sensor agent $b_{1,j^{\prime}}$ will be active. See the right-hand side of Figure 5 for an illustration.

We are now ready to proceed with the proof of Proposition 4.4.

First, recall that by Observation 4.1, at most $n$ cuts can lie in the c-e region. Also recall that from Definition 14, for the circuit encoder $C_{1}$, the blanket-sensor agent $b_{1,j}$, $j\in\{2,\ldots,n\}$ has valuation only in the interval $[j-2,j]$ of the c-e region, i.e. it “monitors” the interval $[j-2,j]$. The blanket-sensor agent $b_{i,j}$ for $i\in\{2,\ldots,p^{C}\}$ is a $(i-1)\frac{\delta^{\rm tiny}}{p^{C}}$-shifted version of $b_{1,j}$. We will make the argument for the blanket-sensor agents of the circuit-encoder $C_{1}$; the argument for any $C_{i}$, with $i\neq 1$ is very similar.

It suffices to prove that if consecutive cuts are too far apart or too close together, some blanket-sensor agent will be active.

Case 1: The cuts are too far apart. First consider the case when two consecutive cuts are too far apart (by more than $1$ plus some inverse-polynomial amount $2\delta$). More formally, assume that there are two cuts $c_{1}$ and $c_{2}$ such that $c_{2}>c_{1}$ and $c_{2}-c_{1}>1+2\delta$. Then, as we explain below, there is some $j\in\{2,\ldots,n\}$ such that some subinterval $I_{j}=[j_{1},j_{2}]\subseteq[j-2,j]$ with $j_{2}-j_{1}>1+\delta$ will receive a single label, either $A_{+}$ or $A_{-}$. In particular, we have the following cases:

There is a $j$ such that $[c_{1},c_{2}]\subseteq[j-2,j]$. In that case, $[c_{1},c_{2}]$ is such a monochromatic subinterval.

There is a $j$ such that $[j-2,j]\subseteq[c_{1},c_{2}]$. In that case, the whole monitored subinterval $[j-2,j]$ is such a monochromatic subinterval.

Case 2: The cuts are too close together. Now consider the case when two consecutive cuts are too close together, closer than $1-2n\delta$. More formally, assume that there are two consecutive cuts $c_{1}$ and $c_{2}$ in the c-e region such that $c_{2}>c_{1}$ and $c_{2}-c_{1}<1-2n\delta$. Since the cuts are close together, there exists a monitored interval that is intersected by both $c_{1}$ and $c_{2}$ and let $[j-2,j]$ be such an interval. Notice that if there exists no other cut that intersects $[j-2,j]$, then $[j-2,c_{1}]\cup[c_{2},j]$ is a union of subintervals of length at least $1+\delta$ that receive the same label, and we are done. Therefore there must exist at least $3$ cuts that lie in $[j-2,j]$. We consider three cases.

There are 5 or more cuts in $[j-2,j]$. This is an easy case to argue, as if that happens, there will be some interval, either $[0,j-2]$ or $[j,n]$ of length $k$ that is only intersected by at most $k-2$ cuts. By Lemma 4.5, some blanket-sensor agent will be active and we are done.

There are 4 cuts in $[j-2,j]$. Consider the intervals $[0,j-2]$ and $[j,n]$. If either $[0,j-2]$ is intersected by at most $(j-2)-2$ cuts or $[j,n]$ is intersected by at most $n-j-2$ cuts, then by Lemma 4.5, some blanket-sensor will be active and we are done. Note also for completeness that, if $j=2$ (respectively $j=n$), it is necessarily the case that $[j-2,n]$ (respectively $[0,j-2]$) is intersected by $n-4$ cuts and Lemma 4.5 again applies. Therefore, we can assume that $j\in\{3,\ldots,n-1\}$, and that there are exactly $(j-2)-1$ cuts in $[0,j-2]$ and $n-j-1$ cuts in $[j,n]$.

Consider the interval $[j,n]$ without loss of generality, as the argument for $[0,j-2]$ is symmetric. By Lemma 4.6, we know that the cuts in $[j,n]$ are $\delta$-close to integer points and particularly, they are $\delta$-close to the midpoints of the monitored intervals $[j,j+2],\ldots,[n-2,n]$. This implies that in the monitored subinterval $[j,j+2]$, the subinterval $[j,j+1-\delta]$ will be a monochromatic interval of label $A_{j}$ for some $A_{j}\in\{A_{+},A_{-}\}$,

In turn, this implies that $[j-1,j]$ has a monochromatic subinterval of length at least $1-\delta$ that receives the label $A_{-j}$, where $A_{-j}\in\{A_{+},A_{-}\}$ is the complementary label to $A_{j}$, for the blanket-sensor agent to not be activated, which is only possible if one of the $4$ cuts in $[j-2,j]$ is $\delta$-close to the integer point $j$. Propagating the effect of this cut sequence/labelling into the monitored interval $[j-2,j]$ in question, we obtain that $[j-2,j-1]$ also contains a monochromatic interval of length at least $1-\delta$ and label $A_{j}$, as otherwise blanket-sensor agent $b_{1,j}$ would be active. From this discussion, it follows that: