  We show that the conditional independence (CI) implication problem with
bounded cardinalities, which asks whether a given CI implication holds for all
discrete random variables with given cardinalities, is co-NEXPTIME-hard. The
problem remains co-NEXPTIME-hard if all variables are binary. The reduction
goes from a variant of the tiling problem and is based on a prior construction
used by Cheuk Ting Li to show the undecidability of a related problem where the
cardinality of some variables remains unbounded. The CI implication problem
with bounded cardinalities is known to be in EXPSPACE, as its negation can be
stated as an existential first-order logic formula over the reals of size
exponential with regard to the size of the input.
