  We consider the problem of conditional independence testing of $X$ and $Y$
given $Z$ where $X,Y$ and $Z$ are three real random variables and $Z$ is
continuous. We focus on two main cases - when $X$ and $Y$ are both discrete,
and when $X$ and $Y$ are both continuous. In view of recent results on
conditional independence testing (Shah and Peters, 2018), one cannot hope to
design non-trivial tests, which control the type I error for all absolutely
continuous conditionally independent distributions, while still ensuring power
against interesting alternatives. Consequently, we identify various, natural
smoothness assumptions on the conditional distributions of $X,Y|Z=z$ as $z$
varies in the support of $Z$, and study the hardness of conditional
independence testing under these smoothness assumptions. We derive matching
lower and upper bounds on the critical radius of separation between the null
and alternative hypotheses in the total variation metric. The tests we consider
are easily implementable and rely on binning the support of the continuous
variable $Z$. To complement these results, we provide a new proof of the
hardness result of Shah and Peters.
