the last three displayed equations and using Chernoff-type bounds, we can get an upper estimate on the probability that $x^S$ is bad in terms of the size of witnesses sets.

\[lemma:badWitness\] Suppose that, for all $i \in [m]$, there are witness sets for $\mathcal{X}_i^+$ and $\mathcal{X}_i^-$ of size at most $M$. Then $\Pr(x^S \textrm{ is bad }) \le 8mM \exp\left(-\frac{\epsilon^3 B}{33}\right)$.

One natural choice of a witness set for, say, $\mathcal{X}_i^+$ is the collection of all of its minimal sets; unfortunately this may not give a witness set of small enough size. But notice that a witness set need not be a subset of $\mathcal{X}_i^+$ (or even $\mathcal{X}$). Allowing elements outside $\mathcal{X}_i^+$ gives the flexibility of obtaining witnesses which are associated to multiple “similar” minimal elements of $\mathcal{X}_i^+$, which is effective in reducing the size of witness sets.

Small witness sets for almost 1-dim columns {#sec:goodWitness}
-------------------------------------------

Given the previous lemma, our task is to find small witness sets. Unfortunately, when the $(\pi_t, a^t)$’s lie in a space of dimension at least 3, $\mathcal{X}_i^+$ and $\mathcal{X}_i^-$ may contain many ($\Omega(n)$) disjoint sets (see Figure \[fig:disjoint3d\]), which shows that in general we cannot find small witness sets directly. This sharply contrasts 