The Rainbow at the End of the Line --- A PPAD Formulation of the Colorful Carathéodory Theorem with Applications

Introduction

Even though the cone version of the colorful Carathéodory theorem guarantees the existence of a colorful choice that ray-embraces the point ${\boldsymbol{b}}$, it is far from clear how to find it efficiently. We call this computational problem the colorful Carathéodory problem (ColorfulCarathéodory). To this day, settling the complexity of ColorfulCarathéodory remains an intriguing open problem, with a potentially wide range of consequences. We can use linear programming to check in polynomial time whether a given colorful choice ray-embraces a point, so ColorfulCarathéodory lies in total function NP (TFNP) , the complexity class of total search problems that can be solved in non-deterministic polynomial time. This implies that ColorfulCarathéodory cannot be NP-hard unless $\textsf{NP}=\textsf{coNP}$ . However, the complexity landscape inside TFNP is far from understood, and there exists a rich body of work that studies subclasses of TFNP meant to capture different aspects of mathematical existence proofs, such as the pigeonhole principle (PPP), potential function arguments (PLS, CLS), or various parity arguments (PPAD, PPA, PPADS) .

Understanding the complexity of ColorfulCarathéodory becomes even more interesting in the light of the fact that the colorful Carathéodory theorem plays a crucial role in proving several other prominent theorems in convex geometry, such as Tverberg’s theorem (and hence the centerpoint theorem ) and the first selection lemma . In fact, these proofs can be interpreted as polynomial time reductions from the respective computational problems, Tverberg, Centerpoint, and SimplicialCenter, to ColorfulCarathéodory. See Section A for more details.

We provide a new upper bound on the complexity of ColorfulCarathéodory by showing that the problem is contained in $\textsf{PPAD}\cap\textsf{PLS}$, implying the first nontrivial upper bound on the computational complexity of computing centerpoints or finding Tverberg partitions.

The traditional proofs of the colorful Carathéodory theorem all proceed through a potential function argument. Thus, it may not be surprising that ColorfulCarathéodory lies in PLS, even though a detailed proof that can deal with degenerate instances requires some care (see Section C). On the other hand, showing that ColorfulCarathéodory lies in PPAD calls for a completely new approach. Even though there are proofs of the colorful Carathéodory theorem that use topological methods usually associated with PPAD (such as certain variants of Sperner’s lemma) , these proofs involve existential arguments that have no clear algorithmic interpretation. Thus, we present a new proof of the colorful Carathéodory theorem that proceeds similarly as the usual proof for Sperner’s lemma . This new proof has an algorithmic interpretation that leads to a formulation of ColorfulCarathéodory as a PPAD-problem.

Preliminaries

The complexity class polynomial parity argument in a directed graph (PPAD) is a subclass of TFNP that contains search problems that can be modeled as follows: let $G=(V,E)$ be a directed graph in which each node has indegree and outdegree at most one. That is, $G$ consists of paths and cycles. We call a node $v\in V$ a source if $v$ has indegree and we call $v$ a sink if it has outdegree . Given a source in $G$, we want to find another source or sink. By a parity argument, there is an even number of sources and sinks in $G$ and hence another source or sink must exist. However, finding this sink or source is nontrivial since $G$ is defined implicitly and the total number of nodes may be exponential.

More formally, a problem in PPAD is a relation $\mathcal{R}$ between a set $\mathcal{I}\subseteq\{0,1\}^{\star}$ of problem instances and a set $\mathcal{S}\subset\{0,1\}^{\star}$ of candidate solutions. Assume further the following.

The set $\mathcal{I}$ is polynomial-time verifiable. Furthermore, there is an algorithm that on input $I\in\mathcal{I}$ and $s\in\mathcal{S}$ decides in time $\operatorname{poly}(|I|)$ whether $s$ is a valid candidate solution for $I$. We denote with $\mathcal{S}_{I}\subseteq\mathcal{S}$ the set of all valid candidate solutions for a fixed instance $I$.

There exist two polynomial-time computable functions $\operatorname{pred}$ and $\operatorname{succ}$ that define the edge set of $G$ as follows: on input $I\in\mathcal{I}$ and $s\in\mathcal{S}_{I}$, $\operatorname{pred}$ and $\operatorname{succ}$ return a valid candidate solution from $\mathcal{S}_{I}$ or $\bot$. Here, $\bot$ means that $v$ has no predecessor/successor.

There is a polynomial-time algorithm that returns for each instance $I$ a valid candidate solution $s\in\mathcal{S}_{I}$ with $\operatorname{pred}(s)=\bot$. We call $s$ the standard source.

Now, each instance $I\in\mathcal{I}$ defines a graph $G_{I}=(V,E)$ as follows. The set of nodes $V$ is the set of all valid candidate solutions $\mathcal{S}_{I}$ and there is a directed edge from $u$ to $v$ if and only if $v=\operatorname{succ}(u)$ and $u=\operatorname{pred}(v)$. Clearly, each node in $G_{I}$ has indegree and outdegree at most one. The relation $\mathcal{R}$ consists of all tuples $(I,s)$ such that $s$ is a sink or source other than the standard source in $G_{I}$.

The definition of a PPAD-problem suggests a simple algorithm, called the standard algorithm: start at the standard source and follow the path until a sink is reached. This algorithm always finds a solution but the length of the traversed path may be exponential in the size of the input instance.

Polyhedral Complexes and Subdivisions.

Linear Programming.

where $j^{\prime}$ is the rank of $j$ in $R$, that is, $({\boldsymbol{r}}_{B,{\boldsymbol{c}}})_{j^{\prime}}$ is the coordinate of ${\boldsymbol{r}}_{B,{\boldsymbol{c}}}$ that corresponds to the $j^{\prime}$th non-basis column with column index $j$ in $A$.

Moreover, we say a nonempty face $f\subseteq\mathcal{P}$ is optimal for a cost vector ${\boldsymbol{c}}$ if all points in $f$ are optimal for ${\boldsymbol{c}}$. We can express this condition using the reduced cost vector. Let $B$ be a basis for a vertex in $f$. Then $f$ is optimal for ${\boldsymbol{c}}$ if and only if

Overview of the PPAD-Formulation

We give a new constructive proof of the cone version of the colorful Carathéodory theorem based on Sperner’s lemma. Using this, we can obtain a PPAD-formulation of ColorfulCarathéodory, by adapting Papadimitriou’s formulation of Sperner’s lemma as a PPAD problem.

The number of fully-labeled simplices is odd.

We construct a Sperner labeling $\lambda$ for $\operatorname{sd}\mathcal{Q}_{\Delta}$ as follows: let ${\boldsymbol{v}}$ be a vertex in $\operatorname{sd}\mathcal{Q}_{\Delta}$, and let $f$ be the face of $\mathcal{F}$ that corresponds to ${\boldsymbol{v}}$. Then, we set $\lambda({\boldsymbol{v}})=i$ if the $i$th color appears most often in the support of $f$. The color controlling property of the cost function $c_{\boldsymbol{\mu}}$ then implies that $\lambda$ is a Sperner labeling. Furthermore, using the properties of the barycentric subdivision and the correspondence between $\mathcal{Q}_{\Delta}$ and $\mathcal{F}$, we can show that one vertex of a fully-labeled $(d-1)$-simplex in $\operatorname{sd}\mathcal{Q}_{\Delta}$ encodes a colorful feasible basis of the ColorfulCarathéodory instance $I$. This concludes a new constructive proof of the colorful Carathéodory theorem using Sperner’s lemma.

To show that ColorfulCarathéodory is in PPAD however, we need to be able to traverse $\operatorname{sd}\mathcal{Q}_{\Delta}$ efficiently. For this, we introduce a combinatorial encoding of the simplices in $\mathcal{Q}_{\Delta}$ that represents neighboring simplices in a similar manner. Furthermore, we describe how to generalize the orientation used in the PPAD formulation of 2D-Sperner to our setting. This finally shows that ColorfulCarathéodory is in PPAD.

To ensure that the complexes that appear in our algorithms are sufficiently generic, we prove several perturbation lemmas that give a deterministic way of achieving this. Our PPAD-formulation also shows that the special case of ColorfulCarathéodory involving two colors can be solved in polynomial time. Indeed, we will see that in this case the polytopal complex $\mathcal{Q}_{\Delta}$ can be made $1$-dimensional. Then, binary search can be used to find a fully-labeled simplex in $\mathcal{Q}_{\Delta}$. In order to prove that the binary search terminates after a polynomial number of steps, we use methods similar to our perturbation techniques to obtain a bound on the length of the $1$-dimensional fully-labeled simplex.

The Colorful Carathéodory Problem is in PPAD

where $j\in[d^{2}]$, $i$ is the color of the $j$th column in $A$, and $0<\varepsilon\leq N^{-3}$ is a suitable perturbation that ensures non-degeneracy of the reduced costs (see ). As stated in the overview, the cost function controls the colors in the support of the optimal faces for parameter vectors in $\mathcal{M}$. The proof of the following lemma can be found in Section D.

Let $i^{\times}\in[d]$ be a color and let ${\boldsymbol{\mu}}\in\mathcal{M}$ be a parameter vector with ${\boldsymbol{\mu}}_{i^{\times}}=0$. Furthermore, let $B^{\star}$ be an optimal feasible basis for $L^{\textsc{CC}}_{\boldsymbol{\mu}}$. Then, $B^{\star}\cap C_{i^{\times}}=\emptyset$.

Then, we define $\mathcal{F}$ as the set of all faces that are optimal for some parameter vector in $\mathcal{M}$:

By definition, $\mathcal{F}\cup\{\emptyset\}$ is a polyhedral subcomplex of $\mathcal{P}^{\textsc{CC}}$. The intersections of the parameter regions with faces of $\mathcal{M}$ induce a subdivision $\mathcal{Q}$ of $\mathcal{M}$:

Let $q\neq\emptyset$ be an element from $\mathcal{Q}_{\Delta}$. Then, there exists unique pair $(f,g)$ where $f$ is a face of $\mathcal{F}$ and $g$ is a face of $\SS$ such that $q=\Phi_{\Delta}(f)\cap g$. Moreover, $q$ is a simple polytope of dimension $\dim g-\dim f$ and, if $\dim q>0$, the set of facets of $q$ can be written as

The set $\mathcal{Q}_{\Delta}$ is a $(d-1)$-dimensional polytopal complex that decomposes $\Delta$. ∎

2 The Barycentric Subdivision

The barycentric subdivision [17, Definition 1.7.2] is a well-known method to subdivide a polytopal complex into simplices. We define $\operatorname{sd}\mathcal{Q}_{\Delta}$ as the set of all simplices $\operatorname{conv}({\boldsymbol{v}}_{0},\dots,{\boldsymbol{v}}_{k})$, $k\in[d]$, such that there exists a chain $q_{0}\subset\dots\subset q_{k}$ of polytopes in $\mathcal{Q}_{\Delta}$ with $\dim q_{i-1}<\dim q_{i}$ and such that ${\boldsymbol{v}}_{i}$ is the barycenter of $q_{i}$ for $i\in[k]$. We define the label of a vertex ${\boldsymbol{v}}\in\operatorname{sd}\mathcal{Q}_{\Delta}$ as follows. By Lemma 4.2, there exists a unique pair $f\in\mathcal{F}$ and $g\in\SS$ with ${\boldsymbol{v}}=\Phi_{\Delta}(f)\cap g$. Then, the label $\lambda({\boldsymbol{v}})$ of ${\boldsymbol{v}}$ is defined as

In case of a tie, we take the smallest $i\in[d]$ that achieves the maximum. Lemma 4.1 implies that $\lambda(\cdot)$ is a Sperner labeling of $\operatorname{sd}\mathcal{Q}_{\Delta}$. In fact, $\lambda$ is a Sperner labeling for any fixed simplicial subdivision of $\Delta$. Now, Theorem 3.1 guarantees the existence of a $(d-1)$-simplex $\sigma\in\operatorname{sd}\mathcal{Q}_{\Delta}$ whose vertices have all $d$ possible labels. The next lemma shows that then one of the vertices of $\sigma$ defines a solution to the ColorfulCarathéodory instance. Here, we use specific properties of the barycentric subdivision.

Let $\sigma\in\operatorname{sd}\mathcal{Q}_{\Delta}$ be a fully-labeled $(d-1)$-simplex and let ${\boldsymbol{v}}_{d-1}$ denote the vertex of $\sigma$ that is the barycenter of a $(d-1)$-face $q_{d-1}=\Phi_{\Delta}(f_{d-1})\cap g_{d-1}\in\mathcal{Q}_{\Delta}$, where $f_{d-1}\in\mathcal{F}$ and $g_{d-1}\in\SS$. Then, the columns from $A_{{\operatorname{supp}\left(f_{d-1}\right)}}$ are a colorful choice that ray-embraces ${\boldsymbol{b}}$.

Our discussion up to now already yields a new Sperner-based proof of the colorful Carathéodory theorem. However, in order to show that $\textsc{ColorfulCarath\'{e}odory}\in\textsf{PPAD}$, we need to replace the invocation of Theorem 3.1 by a PPAD-problem. Note that it is not possible to use the formulation of Sperner from [23, Theorem 2] directly, since it is defined for a fixed simplicial subdivision of the standard simplex. In our case, the simplicial subdivision of $\Delta$ depends on the input instance. In the following, we generalize the PPAD formulation of Sperner in to $\mathcal{Q}_{\Delta}$ by mimicking the proof of Theorem 3.1. For this, we need to be able to find simplices in $\operatorname{sd}\mathcal{Q}_{\Delta}$ that share a given facet. We begin with a simple encoding of simplices in $\operatorname{sd}\mathcal{Q}_{\Delta}$ that allows us to solve this problem completely combinatorially.

We first show how to encode a polytope $q\in\mathcal{Q}_{\Delta}$. By Lemma 4.2, there exists a unique pair of faces $f\in\mathcal{F}$ and $g\in S$ such that $q=\Phi_{\Delta}(f)\cap g$. Since $\mathcal{M}(g)$ is a face of the unit cube, the value of $d-\dim g$ coordinates in $\mathcal{M}(g)$ is fixed to either or $1$. Let $I_{j}\subseteq[d]$, $j=0,1$, denote the indices of the coordinates that are fixed to $j$. Then, the encoding of $q$ is defined as ${\operatorname{enc}\left(q\right)}=\left({\operatorname{supp}\left(f\right)},I_{0},I_{1}\right)$. We use this to define an encoding of the simplices in $\mathcal{Q}_{\Delta}$ as follows. Let $\sigma\in\mathcal{Q}_{\Delta}$ be a $k$-simplex and let $q_{0}\subset\dots\subset q_{k}$ be the corresponding face chain in $\mathcal{Q}_{\Delta}$ such that the $i$th vertex of $\sigma$ is the barycenter of $q_{i}$. Then, the encoding ${\operatorname{enc}\left(\sigma\right)}$ is defined as

In the proof of Theorem 3.1, we traverse only a subset of simplices in the simplicial subdivision, namely $(k-1)$-simplices that are contained in the face $\Delta_{[k]}=\operatorname{conv}\{{\boldsymbol{e}}_{i}\mid i\in[k]\}$ of $\Delta$ for $k\in[d]$. Let $\Sigma_{k}=\left\{\sigma\in\operatorname{sd}\mathcal{Q}_{\Delta}\,\middle|\,\dim(\sigma)=k-1,\ \sigma\subseteq\Delta_{[k]}\right\}$ denote the set of $(k-1)$-simplices in $\operatorname{sd}\mathcal{Q}_{\Delta}$ that are contained in the $(k-1)$-face, where $k\in[d]$, and let $\Sigma=\bigcup_{k=1}^{d}\Sigma_{k}$ be the collection of all those simplices. In the following, we give a precise characterization of the encodings of the simplices in $\Sigma_{k}$. For two disjoint index sets $I_{0},I_{1}\subseteq[d]$, we denote with g(I_{0},I_{1})=\left\{{\boldsymbol{\mu}}\in\mathcal{M}\,\middle|\,j=0,1,\,({\boldsymbol{\mu}})_{i}=j\text{ fori\in I_{j}}\right\} the face of $\mathcal{M}$ that we obtain by fixing the coordinates in dimensions $I_{0}\cup I_{1}$. Let now $T=\left(Q_{0},\dots,Q_{k-1}\right)$, $k\in[d-1]$, be a tuple, where $Q_{i}=\left(S^{(i)},I^{(i)}_{0},I^{(i)}_{1}\right)$, $S^{(i)}\subset\left[d^{2}\right]$, and $I^{(i)}_{0},I^{(i)}_{1}$ are disjoint subsets of $[d]$ with $I^{(i)}_{1}\neq\emptyset$ for $i\in[k-1]_{0}$. We say $T$ is valid if and only if $T$ has the following properties.

We have $I^{(k-1)}_{0}=[d]\setminus[k]$, $\left|I^{(k-1)}_{1}\right|=1$, and the columns in $A_{S^{(k-1)}}$ are a feasible basis for a vertex $f$. Moreover, the intersection $\Phi(f)\cap g\left(I^{(k-1)}_{0}\cup I^{(k-1)}_{1}\right)$ is nonempty.

$I^{(i-1)}_{0}=I^{(i)}_{0}$, $I^{(i-1)}_{1}=I^{(i)}_{1}$, and $S^{(i-1)}=S^{(i)}\cup\left\{a_{i-1}\right\}$ for some index $a_{i-1}\in\left[d^{2}\right]\setminus S^{(i)}$,

or $S^{(i-1)}=S^{(i)}$ and there is an index $j_{i-1}\in[d]\setminus\left(I^{(i)}_{0}\cup I^{(i)}_{1}\right)$ such that either $I^{(i-1)}_{0}=I^{(i)}_{0}$ and $I^{(i-1)}_{1}=I^{(i)}_{1}\cup\left\{j_{i-1}\right\}$, or $I^{(i-1)}_{1}=I^{(i)}_{1}$ and $I^{(i-1)}_{0}=I^{(i)}_{0}\cup\left\{j_{i-1}\right\}$.

For $k\in[d]$, the function ${\operatorname{enc}\left(\cdot\right)}$ restricted to the simplices in $\Sigma_{k}$ is a bijection from $\Sigma_{k}$ to the set of valid $k$-tuples.

Using our characterization of encodings as valid tuples, it becomes an easy task to check whether a given candidate encoding corresponds to a simplex in $\Sigma$.

Let $T=\left(Q_{0},\dots,Q_{k-1}\right)$, $k\in[d-1]$, be a tuple, where $Q_{i}=\left(S^{(i)},I^{(i)}_{0},I^{(i)}_{1}\right)$, $S^{(i)}\subset\left[d^{2}\right]$, and $I^{(i)}_{0},I^{(i)}_{1}$ are disjoint subsets of $[d]$ with $I^{(i)}_{1}\neq\emptyset$ for $i\in[k-1]_{0}$. Then, we can check in polynomial time whether $T$ is a valid $k$-tuple.

In Section E, we show that simplices in $\Sigma$ that share a facet have similar encodings that differ only in one element of the encoding tuples. Using this fact, we can traverse $\Sigma$ efficiently by manipulating the respective encodings.

Let $\sigma\in\Sigma_{k}$ be a simplex and let $q_{0}\subset\dots\subset q_{k-1}$ be the corresponding face chain in $\mathcal{Q}_{\Delta}$ such that the $i$th vertex ${\boldsymbol{v}}_{i}$ of $\sigma$ is the barycenter of $q_{i}$, where $k\in[d]$ and $i\in[k-1]_{0}$. Then, we can solve the following problems in polynomial time: (i) Given ${\operatorname{enc}\left(\sigma\right)}$ and $i$, compute the encoding of the simplex $\sigma^{\prime}\in\Sigma_{k}$ that shares the facet $\operatorname{conv}\left\{{\boldsymbol{v}}_{j}\,\middle|\,j\in[k-1]_{0},\,j\neq i\right\}$ with $\sigma$ or state that there is none; (ii) Assuming that $k<d$ and given ${\operatorname{enc}\left(\sigma\right)}$, compute the encoding of the simplex ${\hat{\sigma}}\in\Sigma_{k+1}$ that has $\sigma$ as facet; and (iii) Assuming that $k>1$ and given ${\operatorname{enc}\left(\sigma\right)}$, compute the encoding of the simplex $\check{\sigma}\in\Sigma_{k-1}$ that is a facet of $\sigma$ or state that there is none.

3 The PPAD graph

Using our tools from the previous sections, we now describe the PPAD graph $G=(V,E)$ for the ColorfulCarathéodory instance. The definition of $G$ follows mainly the ideas from the formulation of Sperner as a PPAD-problem [23, Theorem 2] and the proof of Theorem 3.1.

The graph has one node per simplex in $\Sigma$ that has all labels or all but the largest possible label. That is, we have one node for each $(k-1)$-simplex $\sigma$ in $\Sigma_{k}$ with $[k-1]\subseteq\lambda(\sigma)$. Two simplices are connected by an edge if one simplex is the facet of the other or if both simplices share a facet that has all but the largest possible label. More formally, for $k\in[d]$, we set $V_{k}=\left\{{\operatorname{enc}\left(\sigma\right)}\,\middle|\,\sigma\in\Sigma_{k},\,[k-1]\subseteq\lambda(\sigma)\right\}$, the set of all encodings for $(k-1)$-simplices in $\Sigma_{k}$ whose vertices have all or all but the largest possible label. Then, $V$ is the union of all $V_{k}$ for $k\in[d]$. There are two types of edges: edges within a set $V_{k}$, $k\in[d]$, and edges connecting nodes from $V_{k}$ to nodes in $V_{k-1}$ and $V_{k+1}$. Let ${\operatorname{enc}\left(\sigma\right)},{\operatorname{enc}\left(\sigma^{\prime}\right)}$ be two vertices in $V_{k}$ for some $k\in[d]$. Then, there is an edge between ${\operatorname{enc}\left(\sigma\right)}$ and ${\operatorname{enc}\left(\sigma^{\prime}\right)}$ if the encoded simplices $\sigma,\,\sigma^{\prime}\in\Sigma_{k}$ share a facet $\check{\sigma}$ with $\lambda(\check{\sigma})=[k-1]$, i.e., both simplices are connected by a facet that has all but the largest possible label. Now, let ${\operatorname{enc}\left(\sigma\right)}\in V_{k}$ and ${\operatorname{enc}\left(\sigma^{\prime}\right)}\in V_{k+1}$ for some $k\in[d-1]$. Then, there is an edge between ${\operatorname{enc}\left(\sigma\right)}$ and ${\operatorname{enc}\left(\sigma^{\prime}\right)}$ if $\lambda(\sigma)=[k]$ and $\sigma$ is a facet of $\sigma^{\prime}$. In the next lemma, we show that $G$ consists only of paths and cycles. Please see Section F for the proof.

Let ${\operatorname{enc}\left(\sigma\right)}\in V$ be a node. If ${\operatorname{enc}\left(\sigma\right)}\in V_{1}$ or ${\operatorname{enc}\left(\sigma\right)}\in V_{d}$ with $\lambda(\sigma)=[d]$, then $\deg{\operatorname{enc}\left(\sigma\right)}=1$. Otherwise, $\deg{\operatorname{enc}\left(\sigma\right)}=2$.

This already shows that $\textsc{ColorfulCarath\'{e}odory}\in\textsf{PPA}$. By generalizing the orientation from to our setting, we obtain a function $\operatorname{dir}$ that orients the edges of $G$ such that only vertices with degree one in $G$ are sinks or sources in the oriented graph. In Section F, we show how to compute this function in polynomial time. This finally yields our main result.

ColorfulCarathéodory, Centerpoint, Tverberg, and SimplicialCenter are in $\textsf{PPAD}\cap\textsf{PLS}$.

We give a formulation of ColorfulCarathéodory as PPAD-problem. See Section C for a formulation of ColorfulCarathéodory as PLS-problem. Using the classic proofs discussed in Section A, this then also implies the statement for the other problems.

We set as standard source the -simplex $\{{\boldsymbol{e}}_{1}\}$. We can assume without loss of generality that $\{{\boldsymbol{e}}_{1}\}$ is a source (otherwise we invert the orientation).

Given a valid candidate solution $s\in\mathcal{S}_{I}$, we compute its predecessor and successor with the algorithms from Lemma 4.7 and the orientation function discussed above, with one modification: if a node $s\in V$ is a source different from the standard source in the graph $G$, it encodes by the above discussion a colorful choice $C^{\approx}$ that ray-embraces ${\boldsymbol{b}}^{\approx}$. Let $C$ be the corresponding colorful choice for $I$ that ray-embraces ${\boldsymbol{b}}$. Then, we set the predecessor of $s$ to $C$. The properties of our perturbation ensure that we can compute $C$ in polynomial time. Similarly, if $s$ is a sink in $G$, we set its successor to the corresponding solution for the instance $I$. ∎

A Polynomial-Time Case

Using our techniques from Section 4, we present a weakly polynomial-time algorithm for this case. As described in Section 4.1, we construct implicitly a $1$-dimensional polytopal complex, where at least one edge corresponds to a solution. Then, we apply binary search to find this edge. Since the length of the edges can be exponentially small in the length of the input, this results in a weakly polynomial-time algorithm.

For Sperner’s lemma, it is well-known that a fully-labeled simplex can be found if there are only two labels by binary search. Essentially, this is also what the presented algorithm does: reducing the problem to Sperner’s lemma and then applying binary search to find the right simplex. Since the computational problem Sperner is PPAD-complete even for $d=2$, a polynomial-time generalization of this approach to three colors must use specific properties of the colorful Carathéodory instance under the assumption that no PPAD-complete problem can be solved in polynomial time.

Conclusion

We have shown that ColorfulCarathéodory lies in the intersection of PPAD and PLS. This also immediately implies that several illustrious problems associated with ColorfulCarathéodory, such as finding centerpoints or Tverberg partitions, belong to $\textsf{PPAD}\cap\textsf{PLS}$.

Previously, the intersection $\textsf{PPAD}\cap\textsf{PLS}$ has been studied in the context of continuous local search: Daskalakis and Papadimitriou define a subclass $\textsf{CLS}\subseteq\textsf{PPAD}\cap\textsf{PLS}$ that “captures a particularly benign kind of local optimization”. Daskalakis and Papadimitriou describe several interesting problems that lie in CLS but are not known to be solvable in polynomial time. Unfortunately, our results do not show that ColorfulCarathéodory lies in CLS, since we reduce ColorfulCarathéodory in $d$ dimensions to Sperner in $d-1$ dimensions, and since Sperner is not known to be in CLS. Indeed, if Sperner’s lemma could be shown to be in CLS, this would imply that $\textsf{PPAD}=\textsf{CLS}\subseteq\textsf{PLS}$, solving a major open problem. Thus, showing that ColorfulCarathéodory lies in CLS would require fundamentally new ideas, maybe exploiting the special structure of the resulting Sperner instance. On the other hand, it appears that Sperner is a more difficult problem than ColorfulCarathéodory, since Sperner is PPAD-complete for every fixed dimension larger than $1$, whereas ColorfulCarathéodory becomes hard only in unbounded dimension. On the positive side, our perturbation results show that a polynomial-time algorithm for ColorfulCarathéodory, even under strong general position assumptions, would lead to polynomial-time algorithms for several well-studied problems in high-dimensional computational geometry.

Finally, it would also be interesting to find further special cases of ColorfulCarathéodory that are amenable to polynomial-time solutions. For example, can we extend our algorithm for two color classes to three color classes? We expect this to be difficult, due to an analogy between 1D-Sperner, which is in P, and 2D-Sperner, which is PPAD-complete. However, there seems to be no formal justification for this intuition.

References

Appendix A Polynomial-Time Reductions to the Colorful Carathéodory Problem

We begin by presenting the proofs of the centerpoint theorem, Tverberg’s theorem, and the first selection lemma that use the colorful Carathéodory theorem. Afterwards, we show that these proofs can be interpreted as polynomial-time reductions to the corresponding computational problems.

We call a partition of $P$ into $m$ sets $T_{1},\dots,T_{m}$ a Tverberg $m$-partition if and only if $\bigcap_{i=1}^{m}\operatorname{conv}(T_{i})\neq\emptyset$. Tverberg’s theorem guarantees that there are always large Tverberg partitions.

Note that Theorem A.2 directly implies Theorem A.1. A point ${\boldsymbol{c}}$ in the intersection of a Tverberg $\left\lceil\frac{|P|}{d+1}\right\rceil$-partition has Tukey depth at least $\left\lceil\frac{|P|}{d+1}\right\rceil$ since every halfspace that contains ${\boldsymbol{c}}$ must contain at least one point from each set in the Tverberg partition. We present Sarkaria’s proof of Tverberg’s theorem with further simplifications by Bárány and Onn and Arocha et al. . The main tool is the following lemma that establishes a notion of duality between the intersection of convex hulls of low-dimensional point sets and the embrace of the origin of corresponding high-dimensional point sets. It was extracted from Sarkaria’s proof by Arocha et al. . In the following, we denote with $\otimes$ the tensor product.

Then, the intersection of convex hulls $\bigcap_{i=1}^{m}\operatorname{conv}\left(P_{i}\right)$ is nonempty if and only if $\;\bigcup_{i=1}^{m}{\widehat{P}}_{i}$ embraces the origin.

We claim that $\sum_{i=1}^{m}{\hat{{\boldsymbol{p}}}}_{i}={\boldsymbol{0}}$ and thus ${\boldsymbol{0}}\in\operatorname{conv}\left(\bigcup_{i=1}^{m}{\widehat{P}}_{i}\right)$. Indeed, we have

where we use the fact that $\otimes$ is bilinear.

where we use again the fact that $\otimes$ is bilinear. By the choice of ${\boldsymbol{q}}_{1},\dots,{\boldsymbol{q}}_{m}$, there is (up to multiplication with a scalar) exactly one linear dependency: ${\boldsymbol{0}}=\sum_{i=1}^{m}{\boldsymbol{q}}_{i}$. Thus,

Now, since for all $i\in[m]$ and ${\hat{{\boldsymbol{p}}}}\in{\widehat{P}}_{i}$, the coefficient $\lambda_{i,{\hat{{\boldsymbol{p}}}}}$ is nonnegative and since the sum $\sum_{i\in[m]}\sum_{{\hat{{\boldsymbol{p}}}}\in{\widehat{P}}_{i}}\lambda_{i,{\hat{{\boldsymbol{p}}}}}$ is $1$, we must have $c=1/m\in(0,1]$. Hence, the point $m{\boldsymbol{p}}^{\star}$ is common to all convex hulls $\operatorname{conv}\left(P_{1}\right),\dots,\operatorname{conv}\left(P_{m}\right)$. ∎

Little work is now left to obtain Tverberg’s theorem from Lemma A.3 and the colorful Carathéodory theorem.

The main argument of Bárány’s proof of the first selection lemma is the following lemma.

Let $T_{i}$ denote the $i$th element of $\mathcal{T}$ and color it with color $i$. Now by Theorem 1.1, there exists for every $(d+1)$-subset $I\subseteq[m]$ a colorful choice $C_{I}$ with respect to the color classes $T_{i}$, $i\in I$, that embraces ${\boldsymbol{c}}$. Furthermore, each index set $I$ induces a unique colorful choice $C_{I}$. Thus, there are at least $\binom{m}{d+1}\geq\frac{m^{d+1}}{(d+1)^{d+1}}$ distinct ${\boldsymbol{c}}$-embracing $d$-simplices with vertices in $P$. ∎

The first selection lemma is now an immediate consequence of Lemma A.5 and Theorem A.2.

We define the computational problems that correspond to the centerpoint theorem, Tverberg’s theorem, and the first selection lemma as follows.

a Tverberg $\lceil\frac{n}{d+1}\rceil$-partition.

Finally, interpreting the presented proofs as algorithms, we obtain the following result.

Given access to an oracle for ColorfulCarathéodory, Tverberg can be solved in $O\left(n^{3}\right)$ time. Furthermore, Centerpoint and SimplicialCenter can be solved in $O\left(Ln^{3}\right)$ time, where $L$ is the length of the input.

Appendix B Equivalent Instances of the Colorful Carathéodory Problem in General Position

${\boldsymbol{b}}$ avoids linear subspaces: The point ${\boldsymbol{b}}^{\approx}$ is not contained in the linear span of any $(d-1)$-subset of $\bigcup_{i=1}^{d}C^{\approx}_{i}$.

Polynomial-time equivalent solutions: Given a colorful choice $C^{\approx}\subseteq\bigcup_{i=1}^{d}C^{\approx}_{i}$ that ray-embraces ${\boldsymbol{b}}^{\approx}$, we can compute in polynomial time a colorful choice $C\subseteq\bigcup_{i=1}^{d}C_{i}$ that ray-embraces ${\boldsymbol{b}}$.

Note that by (P2), if $P\subset\bigcup_{i=1}^{d}C^{\approx}_{i}$ ray-embraces ${\boldsymbol{b}}^{\approx}$, then $|P|\geq d$ and thus ${\boldsymbol{b}}^{\approx}\in\operatorname{int}\operatorname{pos}\left(P\right)$. In particular by (P1), ${\boldsymbol{b}}^{\approx}$ is contained in the interior of $\operatorname{pos}(C^{\approx}_{i})$ for $i\in[d]$.

In the next section, we develop tools to ensure non-degeneracy of linear systems by a small deterministic perturbation of polynomial bit-complexity. The approach is similar to already existing perturbation techniques for linear programming as in [9, Section 10-2] and but extends to a more general setting in which the matrix is also perturbed. Based on these results, we then show in Section B.2 how to construct ColorfulCarathéodory instances with properties (P1)–(P3).

In the following, we consider equation systems

We write $p(\varepsilon)=\sum_{i=0}^{k}\alpha_{i}\varepsilon^{i}$. Let $j=\min\{i\in[k]_{0}\mid\alpha_{i}\neq 0\}$. Since $p$ is nontrivial, $j$ exists. Without loss of generality, we assume $\alpha_{j}>0$ (otherwise, we multiply $p(\varepsilon)$ by $-1$). For all $\varepsilon\in\left(0,\frac{1}{2m}\right)$, we have

since $\varepsilon<\frac{1}{2m}$ and hence $p(\varepsilon)\neq 0$ for all $\varepsilon\in\left(0,\frac{1}{2m}\right)$. ∎

where $k$ is the maximum degree of $({\boldsymbol{b}})_{1},\dots,({\boldsymbol{b}})_{d}$. Then, for all $\varepsilon\in\left(0,\frac{1}{2M}\right)$, the linear system $L_{\varepsilon}$ is non-degenerate.

Let now $\tau\in\left(0,\frac{1}{2M}\right)$ be fixed and let $A^{\prime}$ be a submatrix of $A$ such that $A^{\prime}(\tau)$ is a basis of $A(\tau)$. Then, the linear system

has a unique solution ${\boldsymbol{x}}^{\star}$. By Cramer’s rule, we have

where $j\in[d]$ and $A^{\prime}_{j}$ is obtained from the matrix $A^{\prime}$ by replacing the $j$th column with ${\boldsymbol{b}}$. Using Laplace expansion, we can express $\det A^{\prime}_{j}$ as

where $b_{i}=({\boldsymbol{b}})_{i}$ and $C_{i,j}$ is the matrix that we obtain by omitting the $i$th row and the $j$th column from $A^{\prime}_{j}$. Next, we apply the Leibniz formula and write $\det C_{i,j}$ as

B.2 Construction

We now sketch how the remaining construction of the equivalent instance $C_{1}^{\approx},\dots,C_{d}^{\approx},{\boldsymbol{b}}^{\approx}$ in general position proceeds. First, we ensure for $i\in[d]$ that ${\boldsymbol{b}}$ lies in the interior of $\operatorname{pos}\left(C_{i}\right)$ by replacing each point ${\boldsymbol{p}}$ in $C_{i}$ by a set $P_{\varepsilon}({\boldsymbol{p}})$ of slightly perturbed points that contain ${\boldsymbol{p}}$ in the interior of their convex hull. Second, we perturb ${\boldsymbol{b}}$. Lemma B.2 then shows that in both steps a perturbation of polynomial bit-complexity suffices to ensure properties (P2) and (P3).

the vector ${\boldsymbol{b}}$ that is perturbed by a vector from the moment curve. The following lemma shows that for $\varepsilon$ small enough, Property (P2) holds for $C_{1}(\varepsilon),\dots,C_{d}(\varepsilon)$ and ${\boldsymbol{b}}(\varepsilon)$. Let $m$ be the largest absolute value of a coordinate in $C_{1},\dots,C_{d},{\boldsymbol{b}}$ and set $N=d!m^{d}$.

For all $\varepsilon\in\left(0,N^{-2}\right]$, there is no $(d-1)$-subset $P\subset\bigcup_{i=1}^{d}C_{i}(\varepsilon)$ with ${\boldsymbol{b}}(\varepsilon)\in\operatorname{span}P$.

Let $A$ denote the matrix \big{(}C_{1}(\varepsilon)\dots C_{d}(\varepsilon)\big{)}. Then, there exists a subset $P\subset\bigcup_{i=1}^{d}C_{i}(\varepsilon)$ with $|P|<d$ that contains ${\boldsymbol{b}}(\varepsilon)$ in its linear span if and only if the linear system $L_{\varepsilon}:A{\boldsymbol{x}}={\boldsymbol{b}}(\varepsilon)$ is degenerate. The polynomials in $A$ all have degree at most $1$ and the polynomials $({\boldsymbol{b}}(\varepsilon))_{i}$, $i\in[d]$, are $\left(d,2d,\dots,d^{2}\right)$-separated with gap $d-1$. Setting $k_{0}=1$ and $k=d^{2}$ in Lemma B.2 implies that $L_{\varepsilon}$ is non-degenerate for all $\varepsilon\in\left(0,\frac{1}{2M}\right)$, where $M=d!2^{d-1}(d^{2}+1)m^{d}$. Assuming that $m\geq 2$ and that $d\geq 4$, we can upper bound $2^{d}$ by $m^{d}$ and $(d^{2}+1)$ by $d!$. Hence, we have

In the following, we set $\varepsilon_{0}$ to $N^{-2}$. Note that Lemma B.3 holds in particular for $\varepsilon=\varepsilon_{0}$, and thus a deterministic perturbation of polynomial bit-complexity suffices. In the next lemma, we show that the perturbed color classes still ray-embrace the perturbed ${\boldsymbol{b}}$.

For $i\in[d]$, the set $C_{i}(\varepsilon_{0})$ ray-embraces ${\boldsymbol{b}}(\varepsilon_{0})$.

Fix some color class $C_{i}$ and let ${\boldsymbol{m}}_{\varepsilon_{0}}={\boldsymbol{b}}(\varepsilon)-{\boldsymbol{b}}$ be the perturbation vector for ${\boldsymbol{b}}$. Since $C_{i}$ ray-embraces ${\boldsymbol{b}}$, we can express ${\boldsymbol{b}}$ as a positive combination $\sum_{{\boldsymbol{p}}\in C_{i}}\psi_{\boldsymbol{p}}{\boldsymbol{p}}$, where $\psi_{\boldsymbol{p}}\geq 0$ for all ${\boldsymbol{p}}\in C_{i}$. Then,

where $s=\sum_{{\boldsymbol{p}}\in C_{i}}\psi_{\boldsymbol{p}}$. We show that ${\boldsymbol{p}}+\frac{1}{s}{\boldsymbol{m}}_{\varepsilon_{0}}\in\operatorname{pos}\left(P_{\varepsilon_{0}}({\boldsymbol{p}})\right)$ for all ${\boldsymbol{p}}\in C_{i}$. Since $P_{\varepsilon_{0}}({\boldsymbol{p}})\subseteq C_{i}(\varepsilon_{0})$ for all ${\boldsymbol{p}}\in C_{i}$, this then implies ${\boldsymbol{b}}(\varepsilon_{0})\in\operatorname{pos}\left(C_{i}(\varepsilon_{0})\right)$. First, we claim that $s\geq 1$. Indeed, we have

where the last inequality is due to our assumption $\|{\boldsymbol{b}}\|_{1}\geq\|{\boldsymbol{p}}\|_{1}$, for ${\boldsymbol{p}}\in C_{i}$. Now,

As a consequence of Lemma B.3, we can show that colorful choices for the perturbed instance that ray-embrace ${\boldsymbol{b}}(\varepsilon_{0})$, ray-embrace ${\boldsymbol{b}}$ if the perturbation is removed.

Let $C=\left\{{\boldsymbol{c}}_{1},\dots,{\boldsymbol{c}}_{d}\right\}$ be set such that ${\boldsymbol{c}}_{i}\in C_{i}(\varepsilon_{0})$ for $i\in[d]$ and such that ${\boldsymbol{b}}(\varepsilon_{0})\in\operatorname{pos}(C)$. Then, the set $C^{\prime}=\left\{{\boldsymbol{p}}\,\middle|\,i\in[d],\,{\boldsymbol{c}}_{i}\in P_{\varepsilon_{0}}({\boldsymbol{p}})\right\}$ ray-embraces ${\boldsymbol{b}}$.

We prove the statement by letting $\varepsilon$ go continuously from $\varepsilon_{0}$ to . This corresponds to moving the points in $C$ and ${\boldsymbol{b}}(\varepsilon)$ continuously from their perturbed positions back to their original positions. We argue that throughout this motion, ${\boldsymbol{b}}(\varepsilon)$ cannot escape the embrace of the colorful choice.

We can now combine the previous lemmas to obtain our desired result on equivalent instances for ColorfulCarathéodory.

We construct the point sets $C_{1}(\varepsilon_{0}),\dots,C_{d}(\varepsilon_{0})$ and the point ${\boldsymbol{b}}(\varepsilon_{0})$ as discussed above. Since $\log\varepsilon_{0}^{-1}$ is polynomial in the size of $I$, this needs polynomial time. By Lemma B.4, each color class $C_{i}(\varepsilon_{0})$ ray-embraces ${\boldsymbol{b}}(\varepsilon_{0})$, so we can apply Carathéodory’s theorem to reduce the size of $C_{i}(\varepsilon_{0})$ to $d$ while maintaining the property that ${\boldsymbol{b}}(\varepsilon_{0})$ is ray-embraced. Again, we need only polynomial time for this step. Finally, as described at the beginning of this section, we rescale the points to lie on the integer grid in polynomial time. Let $C^{\approx}_{i}$ denote the resulting point set for $C_{i}(\varepsilon_{0})$, where $i\in[d]$, and let ${\boldsymbol{b}}^{\approx}$ be the point ${\boldsymbol{b}}(\varepsilon_{0})$ scaled to the integer grid. Then, properties (P1)–(P3) are direct consequences of this construction and Lemmas B.3, B.4, and B.5. ∎

Appendix C The Colorful Carathéodory Theorem is in PLS

The complexity class polynomial-time local search (PLS) captures the complexity of local-search problems that can be solved by a local-improvement algorithm, where each improvement step can be carried out in polynomial time, however the number of necessary improvement steps until a local optimum is reached may be exponential. The existence of a local optimum is guaranteed as the progress of the algorithm can be measured using a potential function that strictly decreases with each improvement step.

More formally, a problem in PLS is a relation $\mathcal{R}$ between a set of problem instances $\mathcal{I}\subseteq\{0,1\}^{\star}$ and a set of candidate solutions $\mathcal{S}\subseteq\{0,1\}^{\star}$. Assume further the following.

The set $\mathcal{I}$ is polynomial-time verifiable. Furthermore, there exists an algorithm that, given an instance $I\in\mathcal{I}$ and a candidate solution $s\in\mathcal{S}$, decides in time $\operatorname{poly}(|I|)$ whether $s$ is a valid candidate solution for $I$. In the following, we denote with $\mathcal{S}_{\mathcal{I}}\subseteq\mathcal{S}$ the set of valid candidate solutions for a fixed instance $I$.

There exists a polynomial-time algorithm that on input $I\in\mathcal{I}$ returns a valid candidate solution $s\in\mathcal{S}_{\mathcal{I}}$. We call $s$ the standard solution.

There exists a polynomial-time algorithm that on input $I\in\mathcal{I}$ and $s\in\mathcal{S}_{\mathcal{I}}$ returns a set $N_{I,s}\subseteq\mathcal{S}_{\mathcal{I}}$ of valid candidate solutions for $I$. We call $N_{I,s}$ the neighborhood of $s$.

We say a candidate solution $s\in\mathcal{S}$ is a local optimum for an instance $I\in\mathcal{I}$ if $s\in\mathcal{S}_{I}$ and for all $s^{\prime}\in N_{I,s}$, we have $c_{I,s}\leq c_{I,s^{\prime}}$ in case of a minimization problem, and $c_{I,s}\geq c_{I,s^{\prime}}$ in case of a maximization problem. The relation $\mathcal{R}$ then consists of all pairs $(I,s)$ such that $s$ is a local optimum for $I$. This formulation implies a simple algorithm, that we call the standard algorithm: begin with the standard solution, and then repeatedly invoke the neighborhood-algorithm to improve the current solution until this is not possible anymore. Although each iteration of this algorithm can be carried out in polynomial time, the total number of iterations may be exponential. There are straightforward examples in which this algorithm takes exponential time and even more, there are PLS-problems for which it is PSPACE-complete to compute the solution that is returned by the standard algorithm [1, Lemma 15].

Similar to PPAD, each problem instance $I$ of a PLS-problem can be seen as a simple graph searching problem on a graph $G_{I}=(V,E)$. The set of nodes is the set of valid candidate solutions for $I$ and there is a directed edge from $u\in\mathcal{S}_{I}$ to $v\in\mathcal{S}_{I}$ if $v\in N_{I,u}$ and $c_{I,v}<c_{I,u}$ if it is a minimization problem, and otherwise if $c_{I,v}>c_{I,u}$. Then, the set of local optima for $I$ is precisely the set of sinks in $G_{I}$. Because the costs induce a topological ordering of the graph, at least one sinks exists.

C.2 A PLS Formulation of the Colorful Carathéodory Problem

First, we observe that it is sufficient to compute the point ${\boldsymbol{p}}^{\star}\in\operatorname{pos}(C)$ such that

and let ${\boldsymbol{b}}^{\prime}$ denote the vector

and let ${\boldsymbol{c}}_{1},\dots,{\boldsymbol{c}}_{d}$ denote the points in $C$ ordered according to their respective column indices in $A$. Write ${\boldsymbol{x}}$ as

is contained in the positive span of $C$. Furthermore, by the last equality of (8), we have $x_{\boldsymbol{b}}=1$ and thus for $i\in[d]$, the $i$th equality of (8) is equivalent to

Because $B$ is symmetric, this further implies that $B$ is positive semidefinite.

Let now ${\boldsymbol{x}}^{\star}$ be an optimal solution to the convex quadratic program

Having an algorithm to compute the potential function in polynomial time, we only need to translate the above proof of the colorful Carathéodory theorem to the language of PLS.

The problems ColorfulCarathéodory, Centerpoint, Tverberg, and SimplicialCenter are in $\textsf{PPAD}\cap\textsf{PLS}$.

By Theorem 4.9, ColorfulCarathéodory is in PPAD. We now give a formulation of ColorfulCarathéodory as a PLS-problem. Then statement is then implied by Lemma A.7.

Let now $I\in\mathcal{I}$ be a fixed instance and $s\in\mathcal{S}_{I}$ a valid candidate solution. We then define the neighborhood $N_{I,s}$ of $s$ as the set of all colorful choices that can be obtained by swapping one point in $s$ with another point of the same color. The set $N_{I,s}$ can be constructed in polynomial time.

Appendix D The Polytopal Complex

We begin with the following standard lemma that bounds the bit-complexity of basic feasible solutions for a linear program.

Set $A^{\prime}=A_{\operatorname{ind}\left(B\right)}$. By definition of a feasible basis, we have $\det A^{\prime}\neq 0$, and by definition of a basic feasible solution ${\boldsymbol{x}}$, we have $A^{\prime}{\boldsymbol{x}}_{\operatorname{ind}\left(B\right)}={\boldsymbol{b}}$ with ${\boldsymbol{x}}\geq{\boldsymbol{0}}$ and $({\boldsymbol{x}})_{j}=0$ for $j\in[n]\setminus{\operatorname{ind}\left(B\right)}$. Applying Cramer’s rule , we can express the $i$th coordinate of ${\boldsymbol{x}}_{\operatorname{ind}\left(B\right)}$ as $\det A^{\prime}_{i}/\det A^{\prime}$, where $i\in[d]$ and $A^{\prime}_{i}$ is the matrix that we obtain by replacing the $i$th column of $A^{\prime}$ with ${\boldsymbol{b}}$. Using the Leibniz formula, we can bound the determinant:

And similarly, $\left|\det A^{\prime}_{i}\right|\leq N$ can be obtained. Because ${\boldsymbol{x}}$ is a basic feasible solution, we have

Moreover, since $A^{\prime}$ and ${\boldsymbol{b}}$ contain only integer entries, the determinants $\det A^{\prime}$ and $\det A^{\prime}_{i}$ are integers. The implies the statement. ∎

Next, using the techniques from Section B, we can show that a deterministic perturbation of polynomial bit-complexity ensures a non-degenerate intersection of the parameter regions with $\mathcal{M}$.

Let $H^{\prime}$ be a $k$-subset of $H_{\Phi}\cup H_{\square}$, and suppose that $\bigcap_{h\in H^{\prime}}h\neq\emptyset$. We denote with $H^{\prime}_{\Phi}=H^{\prime}\cap H_{\Phi}$ the hyperplanes from $H_{\Phi}$ and similarly, we denote with $H^{\prime}_{\square}=H^{\prime}\cap H_{\square}$ the hyperplanes from $H_{\square}$. Set $R=\left[d^{2}\right]\setminus{\operatorname{ind}\left(B\right)}$ and let $\phi_{1}<\dots<\phi_{n}\in R$ be the indices such that $H^{\prime}_{\Phi}=\{h_{\phi_{1}},\dots,h_{\phi_{n}}\}$, where $n=|H^{\prime}_{\Phi}|$. Then the intersection $\bigcap_{i=1}^{n}h_{\phi_{i}}$ is the solution space to the system of linear equations

where $\operatorname{rank}_{R}(\phi_{i})$ denotes the rank of $\phi_{i}$ in $R$. We write ${\operatorname{ind}\left(B\right)}=\{\beta_{1},\dots,\beta_{d}\}$, with $\beta_{1}<\dots<\beta_{d}$ and ${\boldsymbol{a}}_{i}=\left(A^{-1}_{\operatorname{ind}\left(B\right)}A_{R}\right)_{\operatorname{rank}_{R}(\phi_{i})}$, for $i\in[n]$. Then, (10) is equivalent to

where ${\operatorname{col}\left(\phi_{i}\right)}$ and ${\operatorname{col}\left(\beta_{i}\right)}$ denote the colors of the columns with indices $\phi_{i}$ and $\beta_{i}$, respectively. Thus, $(\ref{eq:red:hphieps})$ is of the form

Set $n^{\prime}=\left|H^{\prime}_{\square}\right|$. Since we assume that the hyperplanes in $H^{\prime}$ have a point in common and since $H^{\prime}_{\square}\subseteq H^{\prime}$, the hyperplanes in $H^{\prime}_{\square}$ fix the values of exactly $n^{\prime}$ coordinates $({\boldsymbol{\mu}})_{j}$ to either or $1$. Let $J$ be the indices of the fixed coordinates and let $J_{i}\subseteq J$ be the indices of the $({\boldsymbol{\mu}})_{j}$ that are set to $i$ for $i=0,1$. Combining this with (13), we can express the intersection of hyperplanes in $H^{\prime}$ as

The matrix $\left(A^{\prime}_{\Phi}\right)_{J}$ is an $n\times(d-n^{\prime})$ integer matrix, whose entries have absolute value at most $N^{c^{\prime}}$ and the polynomials $p_{i}=({\boldsymbol{b}}^{\prime}_{\Phi}-\sum_{j\in J_{1}}(A^{\prime}_{\Phi})_{j})_{i}$, $i\in[n]$, are $(\phi_{1},\phi_{2},\dots,\phi_{n})$-separated with gap . Then, Lemma B.2 implies that for all $\varepsilon\in\left(0,\frac{1}{2M}\right)$, the right hand vector of $(\ref{eq:red:finalls})$ cannot lie in the span of $n-1$ columns of the left hand matrix, where M=d!(d^{2}+1)\big{(}N^{c^{\prime}}\big{)}^{d}. Thus, for $c=\max(3,2c^{\prime})$, we have $N^{-cd}\in\left(0,\frac{1}{2M}\right)$. Since we know that (14) has a solution, it follows that the rank of (14) must be $n$ and thus the intersection $\bigcap_{h\in H^{\prime}}h$ has dimension $d-n-n^{\prime}=d-k$. ∎