  We consider the problem of constructing confidence intervals for the median
of a response $Y \in \mathbb{R}$ conditional on features $X = x \in
\mathbb{R}^d$ in a situation where we are not willing to make any assumption
whatsoever on the underlying distribution of the data $(X,Y)$. We propose a
method based upon ideas from conformal prediction and establish a theoretical
guarantee of coverage while also going over particular distributions where its
performance is sharp. Further, we provide a lower bound on the length of any
possible conditional median confidence interval. This lower bound is
independent of sample size and holds for all distributions with no point
masses.
