Consensus Halving is PPA-Complete

Computational complexity; TFNP; Tucker’s lemma

Introduction

The class TFNP of total search problems in NP (where every instance has an easily-checkable solution) does not seem to have complete problems. Moreover, no problem in TFNP can be NP-complete unless NP=co-NP. Consequently, alternative notions of computational hardness need to be developed and applied in our effort to understand the many and varied problems in TFNP that seem to be intractable.

The complexity class PLS (Johnson et al. ), and the classes PPAD, PPA, and PPP (Papadimitriou ) are subclasses of TFNP associated with various combinatorial principles that guarantee totality. Each principle has a corresponding definition of a computational problem whose totality applies that principle in the most general way possible, and a complexity class of problems reducible to it. In more detail:

PLS consists of problems whose totality invokes the principle that every directed acyclic graph has a sink vertex;

PPAD consists of problems whose totality is based on the principle that given a source in a directed graph whose vertices have in-degree and out-degree at most 1, there exists another degree-1 vertex;

PPA differs from PPAD in that the graph need not be directed; being a more general principle, PPA is thus a superset of PPAD;

PPP, based on the pigeonhole principle, consists of problems reducible to Pigeonhole Circuit.

Of these complexity classes, so far only PLS and PPAD has succeeded in capturing the complexity of “natural” computational problems, and the main point of the present paper is to show for the first time that this is also true for PPA.

The Consensus-halving problem involves a set of $n$ agents each of whom has a valuation function on a 1-dimensional line segment $A$ (the “cake”, in cake-cutting parlance). Consider the problem of selecting $k$ “cut points” in $A$ that partition $A$ into $k+1$ pieces, then labelling each piece either “positive” or “negative” in such a way that each agent values the positive pieces equally to the negative ones. In 2003, Simmons and Su showed that this can always be done for $k=n$; their proof applies the Borsuk-Ulam theorem and is a proof of existence analogous to Nash’s famous existence proof of equilibrium points of games, proved using Brouwer’s or Kakutani’s fixed point theorem. Significantly, Borsuk-Ulam is the undirected version of Brouwer, and already from we know that it relates to PPA, making Consensus-halving a candidate for PPA-completeness. As detailed in Definition 1, we assume that valuations are presented as step functions using the logarithmic cost model of numbers.

The complexity class PPAD has been successful in capturing the complexity of many versions of Nash equilibrium and market equilibrium computation , also cake-cutting . Kintali et al. extend PPAD-completeness to further domains including network routing, coalitional games, combinatorics, and social networks. Rubinstein introduced an exponential-time hypothesis for PPAD to rule out a PTAS for approximate Nash equilibrium computation on bimatrix games. The class PLS represents the complexity of an even larger number of local optimisation problems. These results speak to the importance of PPAD and PLS as complexity classes. By contrast, hitherto the only problems known to be PPA-complete are ones that involve circuits (or equivalently, polynomial-time Turing machines) in their definition, which represented a critique of PPA. Noting that consensus-halving is a kind of social-choice problem, our result can be seen as an example of computational social choice helping to populate “lonely” complexity classes, a phenomenon recently reviewed by Hemaspaandra . The complexity class PPP still suffers from that problem, although the present paper should raise our hope that problems such as Equal Subsets will turn out to be complete for PPP. Oracle separations of all these classes are known from .

The distinction between PPAD and PPA revolves around whether we are searching for a fixpoint in an oriented topological space, or an unoriented one. For example, while Papadimitriou showed that it’s PPAD-complete to find a Sperner solution in a 3D cube, Grigni showed that it’s PPA-complete to find a solution to Sperner’s lemma in a 3-manifold consisting of the product of a Möbius strip and a line segment. The 2-dimensional versions of these results are given in . Despite the apparent similarity between the definitions of PPAD and PPA, there is more progress in basing the hardness of PPA on standard cryptographic assumptions: Factoring can be reduced to PPA (with a randomised reduction) , while so far, the hardness of PPAD has relied on problems from indistinguishability obfuscation ; Garg et al. make progress in weakening the cryptographic assumptions on which to base the hardness of PPAD, but these are still less satisfying than in the case of PPA.

Examples of problems known to be PPA-complete include the following. Aisenberg et al. introduce the problem 2D-Tucker: suppose we have a colouring of an exponentially-fine grid on a square region, the colouring being concisely represented via a circuit. Tucker’s Lemma (the discrete version of Borsuk-Ulam) guarantees that if certain boundary conditions are obeyed, then two adjacent squares in the grid will get opposite colours. 2D-Tucker is the search for such a solution, or alternatively a violation of the boundary conditions. As it happens, we use 2D-Tucker as the starting-point for our reductions here. Deng et al. show PPA-completeness for finding fully-coloured points of triangulations of various non-oriented surfaces; the colourings are presented concisely via a circuit. Recently, Deng et al. showed that Octahedral Tucker is PPA-complete, reducing from 2D-Tucker and using a snake-embedding style technique that packages-up the exponential grid in 2 dimensions, into a grid of constant size in high dimension. Belovs et al. show PPA-completeness for novel problems presented in terms of arithmetic circuits representing instances of the Chevalley-Warning Theorem, and Alon’s Combinatorial Nullstellensatz. There remain other problems in PPA that are not defined in terms of circuits, and are conjectured to be PPA-complete. They include Smith, the problem of finding a second Hamiltonian cycle (given one as part of the input) in a odd-degree graph , and the discrete Ham Sandwich problem (given $n$ sets of $2n$ points in general position in $n$-space, find a hyperplane that splits each of these sets into two subsets of size $n$). Also the problem Necklace-splitting , discussed in , Simmons and Su note the connection with consensus-halving.

A precursor of this paper established that Consensus-halving is PPAD-hard, even when we allow constant-size approximation errors for the agents. Taken with the computational equivalence of Consensus-halving and Necklace-splitting established here, we immediately obtain PPAD-hardness of Necklace-splitting, thus in a well-established sense, Necklace-splitting is computationally intractable. This partially answers a question posed in about the hardness of Necklace-splitting.

2 Overview of the proof

We begin by explaining the ground covered by (where PPAD-hardness was established), and then give an overview of the proof in the present paper. In , each agent $a$ in a Consensus-halving instance, has a particular cut $c(a)$ associated with $a$. In an instance $I_{CH}$ of Consensus-halving, we refer to the interval $A$ on which agents have valuation functions, as the domain of $I_{CH}$.

established PPAD-hardness by reduction from the PPAD-complete problem $\epsilon$-Gcircuit ($\epsilon$-approximate Generalised Circuit) in which the challenge is to find a fixpoint of a circuit in which each node computes (with error at most $\epsilon$) a real value in the range $$, consisting of a function of at most two other nodes in the circuit; these may be certain simple arithmetic operations, or boolean operations (regarding 0 and 1 as representing false and true respectively). In ’s reduction from$\epsilon$-Gcircuit to Consensus-halving, each node$\nu$of a generalised circuit has a corresponding agent$a_{\nu}$, and the value computed at$\nu$is represented by the position taken by the cut$c(a_{\nu})$.$a_{\nu}$’s valuation function is designed to enforce the relationship that$\nu$’s value has with the node(s) providing input to$\nu$. Here we re-use some of the circuit “gate gadgets” of , in particular the boolean ones. A cut that encodes the value computed at a boolean gate is expected to lie in one of two short intervals, associated with true and false.

In moving from PPAD-hardness to PPA-hardness, we encounter a fundamental limitation to the above approach, which is that distinct cuts are constrained to lie in distinct (non-overlapping) regions of $A$, and collectively, the cuts lie in an oriented domain. A new idea is needed, and we construct two special agents (the “coordinate-encoding agents”) along with two cuts that correspond to those agents, which are less constrained regarding where, in principle, they may occur, in a solution to the resulting Consensus-halving instance $I_{CH}$. These two cuts are regarded as representing a point on a Möbius strip, and a distance metric between two pairs of positions for these cuts, does indeed correspond to distance between points on a Möbius strip. New problems arise from this freedom regarding where these cuts can occur, mainly the possibility that one of them may occur outside of the intended “coordinate-encoding region” of the domain of $I_{CH}$. Consequently it may interfere with the circuitry that $I_{CH}$ uses to encode an instance of 2D-Tucker (which, recall, is the problem we reduce from). We deal with this possibility by making multiple copies of the circuit, so that an unreliable copy is “out-voted” by the reliable ones. The duplication (we use 100 copies) of the circuit serves a further purpose reminiscent of the the “averaging manoeuvre” introduced in : we need to deal with the possibility of values occurring at nodes of the circuit that fail to correspond to boolean values. The duplication corresponds to a sampling of a cluster of points on the Möbius strip, most of which get converted to boolean values.

One other significant obstacle addressed here, is due to coordinate-encoding cuts directly representing the location of a point on the Möbius strip with exponential precision. We construct a novel mechanism that reads off $\Theta(n)$ bits of precision from the locations of these cuts, which are then fed in to the circuit-encoding part of the consensus-halving instance. (It is this part of the proof that requires us to work with a definition of $\epsilon$-Consensus-halving that may require $\epsilon$ to be inverse exponential. PPA-hardness for inverse polynomial $\epsilon$ would lead to PPA-completeness of Necklace-splitting, but there seems to be no way to achieve this while reducing from 2D-Tucker in a way that directly encodes the location of a solution to 2D-Tucker.)

Our reductions start out from the 2D-Tucker result of . In Section 3 we give a straightforward proof of PPA-completeness of a restricted version called 2D-MS-Tucker, in which two opposite sides of the domain are each monochromatic. We reduce from this to an artificial-looking problem called Variant Tucker, which is essentially a messy-looking version of 2D-MS-Tucker: the purpose of introducing Variant Tucker is to extract some of the technical clutter from the main event, which is the reduction from there to Consensus-halving (Section 4).

Preliminaries

Simmons and Su were not concerned with computational issues; their result is essentially topological and shows that a solution exists provided that agents’ valuations are infinitely divisible. A computational analogue requires us to identify how functions are represented, and we assume they are given as step functions, or piecewise constant functions, as have also been considered in the cake-cutting literature . A problem instance also includes an approximation parameter $\epsilon$, the allowed difference in value between the two sides of the partition, applicable to any agent.

$\epsilon$-Consensus-halving: An instance $I_{CH}$ incorporates, for each of $i\in[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}$ also incorporates $\epsilon\geq 0$ also represented 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\epsilon$, i.e. each agent has a value in the range $[\frac{1}{2}-\frac{\epsilon}{2},\frac{1}{2}+\frac{\epsilon}{2}]$ for the subintervals labelled $A_{+}$ (thus, also values the subintervals labelled $A_{-}$ in that range).

A version where the domain $A$ is take to be $$is polynomial time equivalent to that of Definition 1 (by scaling the valuations appropriately). In the instances that we construct,$x$is polynomial in$n$but one can equivalently allow$x$to be exponential in$n$; the rescaling changes the size of the encoding of the problem instances by a polynomial factor.

Note that it’s not hard to check that an instance of Consensus-halving is well-formed in the sense that the valuation functions should integrate to 1. Also, note that the bit complexity of numbers involved in an approximate solution need not be excessive, so, together with the proof of we have containment in PPA. A couple of relevant remarks are the following:

Definition 1 allows the accuracy parameter $\epsilon$ to be inverse exponential in $n$, which will be essential for our reduction. In fact, established PPAD-hardness of the problem even for constant $\epsilon$. An interesting open question is whether our PPA-hardness result can be extended for constant or even inverse polynomial $\epsilon$ (which would lead to PPA-completeness for Necklace-splitting; Section 6).

The fact that the functions $\mu_{i}$ are step-functions which integrate to $1$ over the whole interval $A$ is desirable, since this makes the hardness result stronger, compared to arbitrary functions. Note that while the step functions $\mu_{i}$ must have polynomially-many steps, the values they may take can differ by exponential (in $n$) ratios. The “in PPA” result on the other hand is established for arbitrary (bounded, non-atomic) functions, which also makes it as strong as possible, given that it is a containment result.

We assume without loss of generality that we seek solutions to Consensus-halving in which the labels $A_{+}$ and $A_{-}$ alternate as we consider the subintervals formed by the cuts, from left to right. If, say, there are two consecutive subintervals labelled $A_{+}$ in a solution, we could combine them into a single subinterval, leaving us with a un-needed cut, which could be placed at the right-hand endpoint of $A$. We can also assume without loss of generality that the labelling sequence starts with $A_{+}$ on the leftmost subinterval of $A$ defined by the set of cuts.

2 The 2​D2𝐷2D-Tucker problem

We review the total search problem $2D$-Tucker, as defined and shown PPA-complete in . (Definition 2 is a variant of it, that we use, that’s easily seen to be equivalent to the version of .) An instance of $2D$-Tucker consists of a labelling $\lambda:[m]\times[m]\rightarrow\{\pm 1,\pm 2\}$ satisfying the boundary conditions: 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 $(x_{1},y_{1})$, $(x_{2},y_{2})$ ($x_{1},x_{2},y_{1},y_{2}\in[m]$) 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})$.

In the above definition, $m$ is exponential, and $\lambda$ is presented via a circuit that computes it. We use Definition 2, a variant of the above whose PPA-completeness easily follows; it is a more convenient version for us to use.

An instance $I_{T}$ of $2D$-Tucker (with complexity parameter $n$) is defined as follows. Consider the square region $[0,2^{n}]\times[0,2^{n}]$. For $1\leq i,j\leq 2^{n}$, the $(i,j)$-squarelet denotes the unit square whose top right vertex is at $(i,j)$. $I_{T}$ consists of a boolean circuit $C$ having $2n$ input bits representing the coordinates of a squarelet, and 2 output bits representing values $1,-1,2,-2$. $C$’s labelling should obey the boundary conditions of noted above. A solution consists of two squarelets that touch at at least one point, and have opposite labels (i.e. labels that sum to 0).

The containment of the problem in PPA was known from . Aisenberg et al. proved that the problem is also PPA-hard.

3 Organization of the paper

In Section 3, we reduce from 2D-Tucker (the version of Definition 2) to a restricted version 2D-MS-Tucker where two opposite sides of the Tucker square are completely labelled $1$ and $-1$ (a monochromatic sides version). From there, we reduce to an artificial looking variant, Variant Tucker, which however will prove to be very useful for our main reduction to Consensus-halving. Section 4 presents the main reduction and in Section 5, we establish the correctness of the reduction.

Finally, in Section 6, we show a computational equivalence between approximate Consensus Halving and the well-known Necklace Splitting problem.

Reducing from 2​D2𝐷2D-TUCKER to VARIANT-TUCKER

In this section, we reduce from 2D-Tucker to a variant of the Tucker problem, which will be more appropriate to use for proving PPA-hardness of approximate Consensus Halving. The PPA-hardness of the Variant Tucker problem will be established through a sequence of two reductions.

First, we reduce from 2D-Tucker to a version of the problem when two opposite sides of the square are assigned only a single label (with opposite signs), e.g. $1$ and $-1$ (Definition 3). We will refer to this problem as the 2D-MS-Tucker (where MS stands for “monochromatic sides”). See Definition 3, Figure 1.

Then, we reduce from 2D-MS-Tucker to Variant Tucker, by embedding the regions of the 2D-MS-Tucker instance (the squarelets) into a triangle-domain and extending the labelling function to points outside these regions. In this process, there is a designated significant sub-domain which contains the embedded regions along with diagonal strips that emerge from the embedded regions and go out the edge of the triangle-domain. The embedding is such that the lines separating the regions are piecewise rectilinear, with sufficiently long pieces. Intuitively, the regions will not be separated by diagonal lines but rather by “zig-zag” rectilinear lines that approximate the diagonal ones, which results in set of regions that we refer to as tiles. See Figure 2.

An instance $I_{MS}$ of 2D-MS-Tucker (with complexity parameter $n$) is defined as follows. Consider the square region $[0,2^{n}]\times[0,2^{n}]$. For $1\leq i,j\leq 2^{n}$, the $(i,j)$-squarelet denotes the unit square whose top right vertex is at $(i,j)$. $I_{MS}$ consists of a boolean circuit $C$ having $2n$ input bits representing the coordinates of a squarelet, and 2 output bits representing values $1,-1,2,-2$. $C$’s labelling should obey the boundary conditions of noted above, but in addition, all squarelets $(x,y)$ with $y=1$ get labelled 1, and all squarelets $(x,y)$ with $y=2^{n}$ get labelled -1. (So, two opposite sides are monochromatic.) As before, a solution consists of two squarelets that touch at at least one point.

We start from the PPA-hardness of 2D-MS-Tucker.

2D-Tucker is polynomial-time reducible to 2D-MS-Tucker.

Let $I_{T}$ be an instance of 2D-Tucker of size $m\times m$. We will construct an instance $I_{MS}$ of 2D-MS-Tucker of size $3m\times 3m$ such that a solution to $I_{MS}$ will let us efficiently recover a solution to $I_{T}$. We will need to establish three facts, namely that (i) $I_{MS}$ will be defined on square that satisfies the labelling conditions of Definition 3, (ii) that we don’t introduce any solutions during the construction, i.e. that for any solutions to $I_{MS}$ there is a corresponding solution to $I_{T}$ and (iii) that given such a solution to $I_{MS}$, we can find a solution to $I_{T}$ in polynomial time.

First, we augment instance $I_{T}$ with squares of size $m\times m$ attached to the top side (denoted $\mathcal{T}$) and the bottom side (denoted $\mathcal{B}$) of the squareEquivalently, we can attach squares of size $m\times m$ to the left and right sides of the square., which results in a $3m\times m$ rectangle, where only the squarelets with coordinates $(i,j)$ with $i=m+1,\ldots,2m$ and $j=1,\ldots,m$ are labelled (i.e. the squarelets of the original square, before the augmentation). For the labelling of the remaining squarelets, we will explain how to label squarelets $(i,j)$ with $i=1,\ldots,m$, $j=1,\ldots,m$, i.e. the top-attached square $top$; the colouring of the squarelets of the bottom-attached square $bottom$ is symmetric by the fact that the labels of the squarelets of $\mathcal{T}$ and $\mathcal{B}$ satisfy the antipodal labelling of Tucker’s lemma.

To describe the labelling of the square, let $\mathcal{L}$ be the set of squarelets of $top$ that have been assigned a label; obviously at the beginning of the labelling $\mathcal{L}=\emptyset$. The detailed labelling procedure is described in Algorithm 1.

It is not hard to see that the labelling function ensures that “neighbouring” squarelets are either assigned the same label or are assigned labels corresponding only to neighbouring labels of the top side $\mathcal{T}$ or the bottom side $\mathcal{B}$ of the original square. Therefore, if there is a complementary edge that appears in any of the added squares, we can follow the direction of the endpoints of the edge, first towards the centre of the corresponding squares $top$ or $bottom$ (i.e. left or right) and then towards the sides of ($\mathcal{T}$ or $\mathcal{B}$ with directions down or up respectively). This obviously can be done in time polynomial in $m$.

Variant Tucker is essentially a technically-cluttered version of 2D-MS-Tucker. It’s helpful as an intermediate stage towards our eventual goal of Consensus-halving, since the technical clutter emanates from the way we encode 2D-Tucker in terms of Consensus-halving, and by reducing from Variant Tucker, we simplify the proof that our final reduction to Consensus-halving does indeed work.

A subregion of the plane consists of an equivalence class of points $(x,y)$ that are equivalent when their binary expansions are truncated after $n+4$ bits of precision; thus any subregion is a square with an edge length of $\frac{1}{16}2^{-n}$.

Consider pairs $(a,b)$ of non-negative even numbers, for which either $a$ and $b$ are both multiples of 4, or neither are.

Define the $(a,b)$-tile to be a union of 8 subregions arranged as in Figure 2, with central point at $(\frac{1}{16}a\cdot 2^{-n},\frac{1}{16}b\cdot 2^{-n})$, having a height and width of $\frac{1}{4}2^{-n}$. (Thus all horizontal and vertical line segments have coordinates that are multiples of $\frac{1}{16}2^{-n}$.) If $a$ or $b$ is equal to zero, the tile consists of just the parts of this region with non-negative coordinates.

Observe that (for the values of $a,b$ allowed in Definition 5) tiles tessellate the positive quadrant of the plane as in Figure 2.

An instance of Variant Tucker with complexity parameter $n$, consists of a boolean circuit $C$ that takes as input $2n+22$ bits. These input bits represent the coordinates of a point $(x,y)$ for $x,y\in$, each of $x$ and $y$ represented as a bit string with $n+11$ binary places of precision. $C$ has 4 boolean outputs that we use to represent the values $1,-1,2,-2$, respectively as $1110,0001,0111,1000$.Note that we can enforce syntactically that these are only values that the output of the circuit can take. We use this convention instead of the usual $2$-bit circuit output in order to simplify the construction of the Consensus-Halving instance in Section 4. $C$ obeys the following constraints that may be enforced syntactically:

if $y<\frac{3}{8}-x$ then $C$ must output $1$;

if $y>\frac{5}{8}-x$ then $C$ must output $-1$;

if $y>x+\frac{1}{8}$ then the output of $C$ should be opposite to its output on $(1-x,1-y)$, and similarly for points with $y<x-\frac{1}{8}$;

the output value of $C$ may not depend on the last 7 bits of $x$ or $y$;

Moreover, $C$’s output value is constant within tiles (Definition 5, Figure 2): a tile consists of 8 square regions with 128 discrete points along their edges, arranged as in Figure 2.

We allow the following exception to the above rules, which is that for input bit-strings that represent points that lie adjacent to the boundary of any subregion, $C$’s output value is unrestricted.

A solution consists of a sequence of 100 points $(x_{i},y_{i})$ for $1\leq i\leq 100$, where $y_{1}\leq 1-x_{1}$, and for $i>1$ we have $x_{i}=x_{i-1}+2^{-(n+11)}$ and $y_{i}=y_{i-1}-2^{-(n+11)}$, where addition and subtraction are taken modulo 1. These 100 points should contain a set of 10 points that all produce the same output, and another set of 10 points that produce the opposite output. In the case that $y_{1}<100\cdot 2^{-(n+11)}$ and the sequence of points “wraps around”, this property must instead hold after we negate the outputs of the wrapped-around subsequence.

We reduce from 2D-MS-Tucker. Squarelets in an instance $I_{2DMST}$ of 2D-MS-Tucker correspond to tiles in an instance $I_{VT}$ of Variant Tucker as follows.

$I_{2DMST}$ contains squarelets $(i,j)$ for $1\leq i,j\leq 2^{n}$. Each $(i,j)$ squarelet determines the value taken by $C$ on the $(2\cdot 2^{n}+2i+2j,4\cdot 2^{n}-2i+2j)$-tile. With this rule, the squarelets of $I_{2DMST}$ are mapped into tiles in the region $R$ in Figure 3 in such a way that adjacencies are preserved: two squarelets are adjacent if and only if their corresponding tiles are adjacent.

Suppose that the monochromatic sides of $I_{2DMST}$ are squarelets $(i,j)$ with $j=1$ having label 1, and squarelets $(i,j)$ with $j=2^{n}$ having label $-1$. As a result, these squarelets get mapped to sides of the region $R$ that are adjacent to and match the monochromatic regions adjacent to $R$ (the regions where $y<\frac{3}{8}-x$, alternatively $y>\frac{5}{8}-x$).

Any tile in the remaining parts $R^{\prime},R^{\prime\prime}$ of the triangular domain of Figure 3 is allocated the same colour as its closest (Euclidean distance) tile in $R$. That is, the colour of the $(2\cdot 2^{n}+2j,4\cdot 2^{n}+2j)$-tile is allocated to the $(2\cdot 2^{n}+2j-2k,4\cdot 2^{n}+2j+2k)$-tile, for positive integers $k$, and the colour of the $(4\cdot 2^{n}+2j,2\cdot 2^{n}+2j)$-tile is allocated to the $(4\cdot 2^{n}+2j+2k,2\cdot 2^{n}+2j-2k)$-tile, for positive integers $k$. Notice that this rule obeys Property 3 of Definition 6, due to the boundary condition on the colouring of squarelets in $I_{2DMST}$.

Given that $I_{2DMST}$ has a concise circuit that labels its squarelets, it’s not hard to see that the corresponding instance $I_{VT}$ has a concise circuit that takes as input, points in the triangular region (at the slightly higher numerical precision), checks which tile a point belongs to, and labels it according to the above rules.

We claim that for a sequence of 100 points to contain two sets of 10 points having opposite labels, as required for a solution, this will only happen when that sequence crosses two adjacent tiles having opposite labels. Any sequence of 100 points constructed as in the problem definition, may cross the boundaries of subregions in at most 2 places, resulting in at most 4 points where $C$ can disobey the tile colouring due to the exception in item (6). So most of the points in the two sets of 10 oppositely-labelled points must indeed come from two oppositely-labelled tiles.

If this happens in region $R$ of Figure 3, the two tiles correspond directly to two adjacent squarelets in $I_{2DMST}$ having opposite labels. It could also occur in the regions $R^{\prime}$ or $R^{\prime\prime}$, in which case we find a solution in the closest edge of $R$. Suppose the sequence of 100 points “wraps around”, i.e. straddles $R^{\prime}$ and $R^{\prime\prime}$, crossing the line between $(0,0)$ and $(1,0)$ and appearing just to the right of the line between $(0,0)$ and $(0,1)$. Labels get negated at the point where we wrap around, but recall that in this case, we flip the suffix of the sequence occurring in $R^{\prime}$, before applying the test that two sets of 10 points have equal and opposite labels. From such a sequence of points we can identify either of two solutions on the north-west or south-east sides of $R$ that are closest to the sequence of points.

Construction of the Consensus Halving Instance

In this section, we describe how to construct an instance $I_{CH}$ of $\epsilon$-Consensus-halving from an instance of Variant Tucker, for inverse-exponential precision parameter $\epsilon$. At a high level, the domain $A$ of $I_{CH}$ will have two designated regions – a small one, typically containing $2$ cuts in a solution, which represent coordinates of points in the triangular domain of Figure 3 (the “coordinate-encoding region”) and a larger one for the encoding of the labelling circuit (the “circuit-encoding region”). Certain sensoring gadgets will detect the position of coordinate-encoding cuts and will feed this information to a set of gadgets which encode the inputs to the labelling circuit of the Variant Tucker instance. This information will be propagated through the circuit-encoding gadgets and fed back to the coordinate-encoding region. The idea is that two designated agents of the Consensus Halving instance, which will be associated with the coordinate-encoding region, will only be satisfied with the balance between $A_{+}$ and $A_{-}$ if the detected cuts correspond to points on a sequence that is a solution to Variant Tucker (Sections 4.3 and 4.4).

The construction will actually encode multiple copies of the labelling circuit of Variant Tucker for two different reasons. The main reason is that for each copy of the circuit, the cuts in the coordinate-encoding region will encode a different point in the domain, with these points being sufficiently close to each other (this will be achieved by small shifts in the valuation blocks corresponding to the circuits in the coordinate-encoding region) and with all of them lying on the same line segment. We will ensure that a solution to $I_{CH}$ will correspond to (sufficiently many) points of this segment with coordinates in squarelets with equal and opposite labels. The other reason is to deal with “stray cuts”, i.e. cuts that are intended to lie in the coordinate-encoding region but actually cut through the circuit-encoding region. These cuts might “invalidate” the circuits that they cut through, but the construction will ensure that the rest of the circuits will remain unaffected, and there will still be sufficiently many reliable points in the sequence (Section 4.5 and Section 5).

More concretely, given an instance $I_{VT}$ of Variant Tucker with complexity parameter $n$, we will construct an instance $I_{CH}$ of $\epsilon$-Consensus-halving for $\epsilon=2^{-2n}$. Let $A$ denote the Consensus-Halving domain, an interval of the form $[0,x]$ where $x$ is of size polynomial in $n$. Any agent $a$ in $I_{CH}$ has a measure $\mu_{a}:A\longrightarrow\mbox{{IR}}$ which will be represented by a step function (having a polynomial in $n$ number of steps).

. The domain $A$ will consist of two main regions:

The coordinate-encoding region $$ (abbreviated as the c-e region).

The circuit-encoding region $(1,x]$ (abbreviated as R).

Our construction contains $100$ copies of an encoding of the labelling circuit $C$ of Variant Tucker and for the purpose, the circuit-encoding region $R$ will be further divided into $100$ non-intersecting sub-regions $R_{1},\ldots,R_{100}$, one for each copy of the circuit. The regions $R_{i}$ are of equal length and constitute a partition of $R$. We further divide each region $R_{i}$ into three sub-regions $R_{i}^{in}$, $R_{i}^{mid}$ and $R_{i}^{out}$, which again are non-intersecting and partition $R_{i}$. These regions correspond with parts of a circuit that deal respectively with the input bits, the intermediate bits and the outputs.

The instance $I_{CH}$ will have the following sets of agents:

$2$ coordinate-encoding agents $\alpha_{1},\alpha_{2}$ whose valuation functions $\mu_{a_{1}}$, $\mu_{a_{2}}$ are only positive in $\bigcup_{i=1}^{100}R_{i}^{out}$. (See Subsection 4.3 and Figure 7).

100 circuit-encoders $C_{1},\ldots,C_{100}$ (see Subsection 4.4).

Each $C_{i}$ has an associated circuit-encoding region $R_{i}$ of the domain.

With each $R_{i}$, there is a polynomial number of associated circuit-encoding agents. Let ${\cal{A}}_{i}$ be the set of those agents; the set ${\cal{A}}_{i}$ consists of the following sets of agents.

A set ${\cal{S}}_{i}\subset{\cal A}_{i}$ of $8(n+8)+1$ sensor agents with value in $\cup R_{i}^{in}$. Among those, there will be a designated agent that we will refer to as the blanket sensor agent. (See Subsection 4.4.1 and Figures 8 and 9).

A set ${\cal G}_{i}\subset{\cal A}_{i}$ of polynomially-many gate agents, with value in $R_{i}^{in}\cup R_{i}^{mid}\cup R_{i}^{out}$. (See Subsection 4.4.2 and Figure 10).

We associate one cut with each agent; recall that for agent $\alpha$, $c(\alpha)$ is the cut associated with the agent. In a solution to $I_{CH}$, for any agent $\alpha_{i}\in\mathcal{A}_{i}$, these cuts will lie in a specific region, where most of the value of agent $\alpha_{i}$ will be concentrated. We will use $R(\alpha_{i})$ to denote this region. The cuts $c(a_{1}),c(a_{2})$ for the coordinate-encoding agents, are called the coordinate-encoding cuts and the associated region for them is the c-e region, i.e. $R(\alpha_{1})=R(\alpha_{2})=$. We will see that in any solution, either both or one of the coordinate-encoding cuts must lie in the coordinate-encoding region and the other cuts must lie in region $R$. In the event that a coordinate-encoding cut lies outside the c-e region, we refer to it as a stray cut, and while such a cut may initially appear to interfere with the functioning of the circuitry, we will see that the duplication of the circuit using 100 circuit-encoders, allows it to be robust to this problem. (For the appropriate definitions and the details, see Section 5).

2 Useful gadgetry

Parity gadgets: We will use term “element” to refer to a sub-interval $R(\alpha_{i})$ where most of the valuation of agent $\alpha_{1}$ lies. For most elements of our construction, we will assume that for a cut that intersects the block (normally either a rectangle valuation block or two thin blocks of larger height or both), the label to the left of the cut is $A_{+}$ and the label to the right of the cut is $A_{-}$. Since the labels are generally alternating (as otherwise cuts can be merged), to achieve this, we will need to be able to switch the “parity” of the label sequence. This will be achieved with the following very simple parity gadget.

We construct an agent $\alpha_{par}$ that has a single valuation block (i.e. an interval where the agent has a constant, non-zero value) of sufficiently small height and width, in a region between two such distinct valuation blocks of some other agent or agents (where we need the parity switch to take place), and furthermore, no other agent has any value in that interval. Since we are only allowed to use $n$ cuts, in a solution to $I_{CH}$, only one cut is allowed to lie in the region $c(\alpha_{par})$ and therefore intersect this valuation block; obviously the cut has to lie close to the midpoint of the valuation block interval and it will switch the parity of the cut sequence. Throughout the reduction, we will not explain how to explicitly place the parity gadgets in the instance of $I_{CH}$ but rather we will assume without loss of generality that the left-hand sides of the cuts are labelled $A_{+}$, unless stated otherwise.

Bit detection gadgets: Throughout the reduction, we will make use of specific blocks of valuations that we will refer to as bit detection gadgets. The bit detection gadgets will be two thin and dense valuation blocks of relatively large height and relatively small length, situated next to each other, with no other valuation block in between them (e.g. see Figure 7, the valuations of the top two agents in $R_{1}^{out}$ or Figure 6, the values in the $out$ intervals). The precise volume of each valuation block will depend on the corresponding agents, but they will always constitute most of the agent’s valuation over the related interval. The point of these gadgets is that if the discrepancy between $A_{+}$ and $A_{-}$ is (significantly) in the favour of one against the other, there will be a cut intersecting one of the two valuation blocks; which block is intersected will correspond to a $0/1$ value, i.e. a bit that indicates the “direction” of the discrepancy in the two labels.

Boolean gate gadgets: Consider a boolean gate that is either an AND an OR or a NOT gate, denoted $g_{\land}$, $g_{\lor}$ and $g_{\neg}$ respectively. Let $in_{1}$, $in_{2}$ and $out$ be intervals such that $|in_{1}|=|in_{2}|=|out|=1$. We will encode these gates using the following gate-gadgets.

Note that the gadget corresponding to the NOT gate only has one input, whereas the gadgets for the AND and OR gates have two inputs. In the interval $out$, each gadget has two bit detection gadgets - in the case of the NOT gate these are even, but in the case of the AND and OR gates, they are uneven. (see Figure 6). Also note that for the inputs, as well as the output of the NOT gate, the label on the left-hand side of the cut is $A_{+}$ and the label on the right-hand side will be $A_{-}$, whereas for the outputs to the OR and AND gate, the label on the left-hand side of the cut is $A_{-}$ and the label on the right hand side is $A_{+}$ . This can be achieved with the appropriate use of parity gadgets (see Figure 6).

The boolean gate gadgets described above encode valid boolean NOT, OR and AND operations.

3 The coordinate-encoding agents

The coordinate-encoding region $$is the region from which the value of the solution to$\epsilon$-Consensus-halving will be read and will be translated to coordinates of a grid point on$I_{VT}$. Associated with this region, there are$2$coordinate-encoding agents$\alpha_{1}$and$\alpha_{2}$. However, these agents will have value in the subinterval$$and all of their value will lie in the circuit-encoding region$R_{i}$and specifically in$\bigcup_{i=1}^{100}R_{i}^{out}$.

The value of the c-e agents in $R_{i}^{out}$ will corresponds to the feedback mechanism from the blanket sensor agent of $R_{i}$ (see Subsection 4.4.1) and the feedback mechanisms from the gate-agents corresponding to the output gates of the circuit (see Subsection and 4.6). Concretely the valuation of the coordinate-encoding agents is defined as follows:

Note that for each $i=1,\ldots,100$, the value of the agent in $R_{i}$ adds up to $1/100$ and therefore the agent’s total valuation in $R$ is $1$. Intuitively, each coordinate encoding region has values that consist of the following components in each region $R_{i}$:

A bit detection gadget positioned in the interior of the interval where the bit detection gadget of the corresponding blanket sensor agent is situated (see also Subsection 4.4.1).

Two blocks of valuation situated in the interior of the intervals where the bit detection gadgets of the output gate agents are situated in $R_{i}^{out}$ (see also Subsection 4.4.2). There are four output gate agents in each $R_{i}$; $\alpha_{i}$ has value in the corresponding intervals for two of those and $\alpha_{2}$ has value in the corresponding intervals for the other two.

4 The circuit encoders

In this subsection, we explain how to design the circuit-encoders $C_{1},\ldots,C_{100}$. Recall that these are sets of agents of $I_{CH}$ that encode the labelling circuit $C$ of Variant Tucker, including the inputs and the outputs to the circuit, via the use of sets ${\cal A}_{1},\ldots{\cal A}_{100}$ of circuit-encoding agents. In the set ${\cal A}_{i}$, there are two different types of circuit-encoding agents:

The sensor agents ${\cal S}_{i}$ that are responsible for extracting the binary representation of the positions of the cuts in the c-e region, which will be used as inputs to the remaining circuit-encoding agents. These agents have value in $\cup R_{i}^{in}$. Among those agents, there is a designated agent $\alpha_{i}^{bs}$ that we refer to as the blanket sensor agent.

In the next subsections, we design the values of those agents explicitly. We will first explain how to construct the circuit-encoder $C_{1}$ and then based on this, we will construct the remaining circuit-encoders $C_{2},\ldots,C_{100}$.

In this subsection, we will design the set of sensor agents, which is perhaps the most vital part of the construction. Roughly speaking, these agents will be responsible for detecting the position of a cut in the c-e region and extracting its binary representation. The set ${\cal S}_{1}$ contains $8(n+8)+1$ sensor agents, which consist of

the blanket sensor agent $\alpha_{1}^{bs}$, that is responsible for detecting large discrepancies in the lengths of $A_{+}$ and $A_{-}$ in the c-e region,

For an illustration, see Figures 7, 8 and 9. We design these sets of agents below.

The blanket sensor agent

The valuation of the blanket sensor agent $\alpha_{1}^{bs}$ is defined as:

The blanket sensor agent is responsible for detecting large enough discrepancies in $A_{+}$ and $A_{-}$. As we will see, if such a discrepancy exists, the blanket sensor agents will provide feedback to the c-e agents, making sure that this is not a solution to $I_{CH}$. We state the lemma here but postpone its proof for Section 5.

Let $A_{+}^{(c-e)}$ and $A_{-}^{(c-e)}$ be the total fraction of the c-e region labelled $A_{+}$ and $A_{-}$ respectively. The blanket sensor agents ensure that in a solution to $I_{CH}$, it holds that

Whenever the blanket sensor agent $\alpha_{i}^{bs}$ does detect such a discrepancy (and therefore the cut $c(\alpha_{i}^{bs})$ in $R(\alpha_{i}^{bs})$ assumes one of the extreme positions, left or right), we will say that the blanket sensor agent is active and that it overrides the circuit $C_{i}$. Otherwise, we will say that the blanket sensor agent is passive.

The bit extractors

The second set of agents in ${\cal S}_{1}$ will be responsible for detecting the position of the cuts and extracting their binary expansion. To be more precise, these agents will extract $8$ binary numbers of length $n+8$, from $8$ consecutive intervals of length $1/8$ each, which span the c-e region, and this number will encode the position of the cut within the interval. We will refer to these extracted binary strings as the raw data.

Lemma 4.2 ensures that it is not possible for two cuts to intersect the same interval of length $1/8$. If for some interval of length $1/8$ there are no cuts intersecting it, the corresponding bit extractors will output a binary string which will consists of only $1$’s or only ’s; we will refer to such bit strings as solid.

A binary string is called solid if either all of its bits are $1$ or all of its bits are .

If the interval is intersected by one cut, the bit extractors will output a binary string consisting of a non-trivial mixture of ’s and $1$’s.

The raw data extracted from the bit-extractors will be fed into the encoders of the input gates of $C_{i}$, and in particular to the pre-processing circuit $C_{i}^{\textrm{pre}}$ that will transform the extracted information into the binary representation of the coordinate of a point $(x,y)$ on the domain, which will then be fed into the encoding $C_{i}^{VT}$ of the labelling circuit $C$. We explain this in more detail in Section 4.4.2.

For each bit extractor, there are another $n+7$ sensor agents that will have exactly the same value in $$. In particular, this value will be$1/10$in volume, spanning over an interval of length$1/8$. We will refer to those$n+8$sensor agents as c-e identical, precisely because they have the same valuation in the c-e region. There will be exactly$8$sets of$n+8$c-e identical sensor agents. For$i=2,\ldots,8$, the values of the c-e identical agents for$i$will be shifted by$1/8$to the right, compared to the values of the c-e identical agents of$i-1$. Therefore, the set of sensor agents covers the whole c-e region. (See Figure 9).

The agents in $\mathbf{[0,1/8]}$: First, we will define the valuations of agents $\alpha_{1,k}^{s},\ldots,\alpha_{1,n+8}^{s}$ and we will explain how to construct the valuations of the remaining agents from these agents. Note that these agents are c-e identical. First, let

Given a cut in the interval where $n+8$ c-e identical bit extractors have their value in the c-e region (e.g. the interval $[0,1/8]$ for the first $n+8$ c-e identical agents), the bit extractors recover a binary string of length $n+8$ which encodes the cut position in that interval.

$\mu_{\alpha_{jk}^{s}}(x)=\mu_{a_{(j-1),k}^{s}}(y)+1/8$ if $x\in\mathcal{R}_{j}$ and

$\mu_{\alpha_{jk}^{s}}(x)=\mu_{a_{1k}^{s}}(y)$ if $x\in\mathcal{R}_{j}$, $y\in\mathcal{R}_{1}$ and $y=h_{\mathcal{R}_{1},\mathcal{R}_{j}}(x)$.

The role of the bit extractors is to cover the whole c-e region in order to be able to detect the positions of cuts that lie anywhere in it. The reason for having $8$ shifted versions instead of a single detector is that the bit-extraction units are only operative if their inputs are intersected by at most one cut. Using these smaller valuation blocks, this guarantee is provided by the blanket sensor agent, according to Lemma 4.2.

The bit-extractors $\mathcal{S}_{i}$ can extract the binary representation of a point $(x,y)$ on the domain, represented by a set of cuts in the c-e region.

The proof of the proposition is left for Section 5.

4.2 The gate agents

Implementing the circuit using the gate gadgets

Concretely, we will use the gate gadgets from Subsection 4.2 that will encode the gates of the circuit. For each gate of $C_{1}$, we will associate a gate agent $\alpha_{1}^{g},\ldots,\alpha_{|C_{1}|}^{g}$ with valuation given by the gadget

where the output of the bit extractors of Subsection 4.4.1 lie (see Subsection 4.4.1 and Figure 8). In simple words, the intervals from which the binary outcomes of the bit extractors are read (via the position of the cuts) are the input intervals to the input gate gadgets of $C_{1}^{\textrm{pre}}$. The output intervals $out^{i}$ are subintervals of $R_{1}^{mid}$ that do not overlap with any other intervals in $R_{1}^{mid}$.

Next, for any agent $\alpha_{i}^{g}\in\{\alpha^{g}_{L+1},\ldots,\alpha^{g}_{|C_{1}|-4}\}$,

$in_{1}^{i}$ and $in_{2}^{i}$ are the intervals $out^{j_{1}}$ and $out^{j_{2}}$ of agents $\alpha_{j_{1}}^{g},\alpha_{j_{2}}^{g}\in\mathcal{G}_{1}$, where $\alpha_{j_{1}}^{g},\alpha_{j_{2}}^{g}$ correspond to the inputs $g_{j_{1}}$ and $g_{j_{2}}$ of gate $g_{i}$ in $C_{1}$

$out^{i}$ is an interval of $R^{mid}_{i}$ which does not overlap with any interval $in_{1}^{k},in_{2}^{k}$ or $out^{k}$, for any $k<i$.

The definitions for the intervals $in_{1}^{i}$ and $out^{i}$ of the agents $\alpha_{i}^{g}$ that correspond to NOT gates are very similar.

Finally, for the gate agents $\alpha_{i}^{g}\in\{\alpha^{g}_{|C_{1}|-3},\ldots,\alpha^{g}_{|C_{1}|}\}$, corresponding to the output gates $g_{out}^{1},g_{out}^{2},g_{out}^{-1}$ and $g_{out}^{-2}$ of $C_{1}$, we have that

$in_{1}^{i}$ and $in_{2}^{i}$ are the intervals $out^{j_{1}}$ and $out^{j_{2}}$ of agents $\alpha_{j_{1}}^{g},\alpha_{j_{2}}^{g}\in\mathcal{G}_{1}$, where $\alpha_{j_{1}}^{g},\alpha_{j_{2}}^{g}$ correspond to the inputs $g_{j_{1}}$ and $g_{j_{2}}$ of gate $g_{i}$ in $C_{1}$.

$out^{i}$ is one of the subintervals in which a $1/400$-fraction of the value of a coordinate-encoding agent lies, i.e.

Note that there are $4$ such subintervals and the output of each of the four gates $g_{i}$ for $i\in\{|C_{1}|-3,\ldots,|C_{1}|\}$ lies in one of those subintervals.

As we mentioned earlier, the pre-processing circuit inputs the raw data extracted from the circuit encoders and outputs the binary expansion of the coordinate of the detected position $(x,y)$ in the c-e region. Then, the outcome of $C_{1}^{\textrm{pre}}$ is fed directly into the input gates of $C_{1}^{VT}$ and the information is propagated through the circuit, resulting in the assignment of a label for the encoded point. Here, we explain the operation of the pre-processing circuit in more detail.

$x=\frac{k-1}{8}+\frac{B_{k}}{2^{n+8}}$, if $b_{1}$ is a string of $1$’s and

$x=\frac{k-1}{8}+\frac{2^{n+8}-B_{k}}{2^{n+8}}$, if $b_{1}$ is a string of ’s.

In simple words, the circuit reads the raw data from the bit-encoders for regions $R_{1},\ldots,R_{k-1}$ and depending on whether it is a string of $1$’s or a string of ’s, it interprets the bit extracted from $R_{k}$ as the distance from the left or the right endpoint of the interval respectively. In the event where $c(\alpha_{1})$ intersects $R_{1}^{1/8}$, the information is obtained similarly from the bit-extractors of region $R_{2}^{1/8}$ (which have to output a solid string by Lemma 4.2, as discussed previously). Specifically, the pre-processing circuit in that case sets:

$x=\frac{B_{k}}{2^{n+8}}$, if $b_{2}$ is a string of ’s and

$x=\ \frac{2^{n+8}-B_{k}}{2^{n+8}}$, if $b_{2}$ is a string of $1$’s.

where $b_{2}$ is the binary string extracted from the bit-extractors of $R_{2}^{1/8}$.

Now consider the case when there is only one cut in the c-e region. In that case, in a solution to $I_{CH}$, the cut can not intersect regions $R_{1}^{1/8}$ or $R_{8}^{1/8}$ as that would violate Lemma 4.2 and there exist regions both to the left and to the right of the region $R_{k}^{1/8}$ intersected by the cut which provide solid strings as inputs to the pre-processing circuit. In that case, the pre-processing circuit sets $x=0$ and

$y=\frac{k}{8}-\frac{B_{k}}{2^{n+8}}$, if $b_{1}$ is a string of ’s and

$y=\frac{k}{8}-\frac{2^{n+8}-B_{k}}{2^{n+8}}$, if $b_{1}$ is a string of $1$’s.

In the event that some cut lies exactly in the boundary of two consecutive regions $R_{j-1}^{1/8}$ and $R_{j}^{1/8}$ for some $j\in\{2,\ldots,8\}$, the only difference is that the circuit does not receive an input with a non-trivial mix of $1$’s and ’s for this cut, but rather a sequence of $k-1$ solid strings consisting of $z$’s followed by a solid string of $|1-z|$’s, extracted by the bit-extractors of region $R_{k}^{1/8}$. In that case, the circuit operates exactly as before, with the cut lying in region $R_{k}^{1/8}$.

The encoding of the circuit $C_{1}^{\textrm{main}}$ will consist of the encodings of two subcircuits, the labeling circuit $C_{i}^{VT}$ of Variant Tucker and the XOR operator circuit.

The input to the circuit $C_{1}^{VT}$ is the binary representations of the coordinates of a grid point within a squarelet of $I_{VT}$ outputted by the pre-processing circuit. Recall that each squarelet contains a set of grid points with a resolution of $2^{7}$ in each dimension (see Figure 2). The output is a label $\{\pm 1,\pm 2\}$; in particular, the output gates of $C$ are $g_{out}^{1},g_{out}^{-1},g_{out}^{2}$ and $g_{out}^{-2}$ and the following correspondence is syntactically enforced (Definition 6):

The XOR operator circuit: This circuit will perform a simple operation, using the raw data gathered from the bit-extractors and the ouputs of $C_{1}^{VT}$. Recall the definition of the solid strings as well as the regions $R_{j}^{1/8}$ for $j=1,\ldots,8$ from earlier, with $b_{j}$ denoting the raw data outputted by the bit-extractors of region $R_{j}^{1/8}$. Let $rep(b)$ denote any bit of a solid bit-string $b$ (since they are all the same) and let $\overline{rep(b)}$ denote its complement. First, a sub-circuit $C_{i}^{\textrm{det}}$ will perform the following operation on the raw data.

If the output $b_{1}$ of the bit-extractors in $[0,1/8]$ is solid, then output a bit $z=\overline{rep(b_{1})}$.

If the output $b_{1}$ of the bit-extractors in $[0,1/8]$ is not solid, then output a bit $z=rep(b_{2})$.

Note that by Lemma 4.2, if $b_{1}$ is not solid, $b_{2}$ has to be solid. Finally, if $z_{1}z_{2}z_{3}z_{4}$ are the outputs of $C_{i}^{VT}$, the XOR operator outputs a string $y_{1}y_{2}y_{3}y_{4}$ with $y_{i}=z_{i}\oplus z$, for $i=\{1,2,3,4\}$, where $\oplus$ denotes the Exclusive-OR operation. The effect of this operation is that either the circuit produces the same label or all the outputs are flipped and the circuit produces the opposite label, depending on the raw data. This will be particularly useful when arguing about the stray cut in Section 5.

For an illustration of the encoded circuits, see Figure 11.

It is not hard to see that our gadgets simulate the operation of the circuit. The proof of the following proposition basically follows from the construction and is included in Section 5.

We construct the circuit-encoder $C_{i}$ as follows. For $j=1,\ldots,|A_{i}|$, let $a_{ij}$ denote the $j$’th circuit-encoding agent in $\mathcal{A}_{i}$. Then for all $i=2,\ldots,100$, for all $j\in\{1,\ldots,|A_{i}|\}$,

let $\mu_{a_{ij}}(x)=\mu_{a_{1j}}(y)$ if $x\in R_{i}$, $y\in R_{1}$ and $y=h_{R_{1},R_{i}}(x)$.

let $\mu_{a_{ij}}((x+(i-1)\cdot 2^{-(n+11)})\mod(1))=\mu_{a_{1j}}(x)$, if $x\in$, i.e. if $x$ is in the c-e region.

The second of these items says that in the c-e region, the valuation function of the agents that make up $C_{i}$ differ from those of $C_{1}$ by having been shifted to the left by $2^{-(n+11)}\cdot(i-1)$, where this shift “wraps around” in the event that we shift below $1$ (the left-hand point of the c-e region). In other respects, $C_{i}$ is an exact copy of $C_{1}$, save that $C_{i}$’s internal circuitry lies in $R_{i}$ rather than $R_{1}$.

The virtual cuts: For the circuit encoders $C_{2},\ldots,C_{100}$ it will often be useful to think of the following alternative interpretation of their inputs. Consider the two cuts (the case of one cut is similar) in the c-e region, at positions $c^{1}_{1},c^{1}_{2}$, encoding a point $(x,y)$ of the domain (also see Section 4.5). Since $C_{2}$ is a version of $C_{1}$ where all the values in the c-e region are shifted by $2^{-(n+11)}$ to the left (wrapping around for some valuations), we can equivalently think of the output of $C_{2}$ as what the output of $C_{1}$ would have been if the cuts had been moved slightly to the right, i.e. to $c^{2}_{1}=c_{1}+2^{-(n+11)}$ and $c^{2}_{2}=c_{2}+2^{-(n+11)}$ respectively. In other words, for each circuit-encoder $C_{i}$, we can think of its output as the output of $C_{1}$ if the cut were placed at $c^{i}_{1}$ and $c^{i}_{2}$. We will refer to such cuts as virtual cuts.

In this subsection, we explain how to obtain a solution to $I_{VT}$ from a solution to $I_{CH}$. Recall from Section 3 that a solution to $I_{VT}$ is a sequence of points $(x_{1},y_{1}),(x_{2},y_{2}),\ldots,(x_{100},y_{100})$ of the (discrete) domain, lying on a line segment such that two sets of at least $10$ of these points each have coordinates in squarelets of equal and opposite labels. Specifically, for each point $(x_{i},y_{i})$ on the segment, with $i<100$, it holds that $x_{i+1}=x_{i}+2^{-(n+11)}$ and $y_{i+1}=y_{i}-2^{-(n+11)}$ (See Figure 2).