  Causal effect identification considers whether an interventional probability
distribution can be uniquely determined from a passively observed distribution
in a given causal structure. If the generating system induces context-specific
independence (CSI) relations, the existing identification procedures and
criteria based on do-calculus are inherently incomplete. We show that deciding
causal effect non-identifiability is NP-hard in the presence of CSIs. Motivated
by this, we design a calculus and an automated search procedure for identifying
causal effects in the presence of CSIs. The approach is provably sound and it
includes standard do-calculus as a special case. With the approach we can
obtain identifying formulas that were unobtainable previously, and demonstrate
that a small number of CSI-relations may be sufficient to turn a previously
non-identifiable instance to identifiable.
