I have a quantum map described by the following Kraus operators
$$A_0 = c_0 \begin{pmatrix} 1 & 0\\ 0 & 1 \end{pmatrix}, \qquad A_1 = c_1 \begin{pmatrix} 1 & 0\\ 0 & -1 \end{pmatrix},$$
such that $c_0^2 + c_1^2 = 1$. I want to know what is a complementary map and how to construct the same for the above-mentioned channel?
Edit 1: Checked for some literature. Here is the definition of the complementary map equations 37 and 38.
Let's start by finding a complementary channel for any channel given by a Kraus representation $$ \Phi(X) = \sum_{k=1}^n A_k X A_k^{\dagger}. $$ To make the necessary equations clear, let us assume that the channel has the form $\Phi:\mathrm{L}(\mathcal{X})\rightarrow \mathrm{L}(\mathcal{Y})$ for finite-dimensional Hilbert spaces $\mathcal{X}$ and $\mathcal{Y}$. Let us also define $\mathcal{Z} = \mathbb{C}^n$; the complementary channel we will define will take the form $\Psi:\mathrm{L}(\mathcal{X})\rightarrow \mathrm{L}(\mathcal{Z})$. (For the channel in the question itself, we will have $\mathcal{X}$, $\mathcal{Y}$, and $\mathcal{Z}$ all equal to $\mathbb{C}^2$, but it helps nevertheless to assign different names to these spaces.)
Define an operator $$ A = \sum_{k=1}^n A_k \otimes | k\rangle, $$ which is a linear operator mapping $\mathcal{X}$ to $\mathcal{Y}\otimes\mathcal{Z}$. This gives us a Stinespring representation $$ \Phi(X) = \operatorname{Tr}_{\mathcal{Z}} \bigl( A X A^{\dagger}\bigr). $$ The channel $$ \Psi(X) = \operatorname{Tr}_{\mathcal{Y}} \bigl( A X A^{\dagger}\bigr) $$ is therefore complementary to $\Phi$. We can simplify this expression by observing that $$ A X A^{\dagger} = \sum_{j=1}^n \sum_{k=1}^n A_j X A_k^{\dagger} \otimes | j \rangle \langle k |, $$ so that $$ \Psi(X) = \sum_{j=1}^n \sum_{k=1}^n \operatorname{Tr}\bigl(A_j X A_k^{\dagger}\bigr) | j \rangle \langle k |. $$ There's not too much more we can do with this, except perhaps to use the cyclic property of the trace to obtain the expression $$ \Psi(X) = \sum_{j=1}^n \sum_{k=1}^n \operatorname{Tr}\bigl(A_k^{\dagger} A_j X\bigr) | j \rangle \langle k |. $$
Now let's plug in the specific operators from the question to obtain $$ \Psi(X) = c_0^2 \operatorname{Tr}(X) | 0 \rangle \langle 0 | + c_1^2 \operatorname{Tr}(X) | 1 \rangle \langle 1 | + c_0 c_1 \operatorname{Tr}(\sigma_z X) | 0 \rangle \langle 1 | + c_0 c_1 \operatorname{Tr}(\sigma_z X) | 1 \rangle \langle 0 |. $$ Here $\sigma_z$ denotes the Pauli-Z operator, which we get because $A_0^{\dagger} A_1 = A_1^{\dagger}A_0 = c_0 c_1 \sigma_z$. (I am assuming $c_0$ and $c_1$ are real numbers.) The expression may look a bit nicer in matrix form: $$ \Psi\begin{pmatrix} \alpha & \beta\\ \gamma & \delta\end{pmatrix} = \begin{pmatrix} c_0^2(\alpha + \delta) & c_0 c_1 (\alpha - \delta)\\ c_0 c_1 (\alpha - \delta) & c_1^2 (\alpha + \delta) \end{pmatrix}. $$
Finally, the question asks for Kraus operators of $\Psi$, which we can get by computing the Choi operator of $\Psi$. In general, this is the operator $$ J(\Psi) = \sum_{j=1}^n\sum_{k=1}^n \Psi(|j\rangle\langle k|) \otimes |j\rangle\langle k|, $$ and in this particular case we obtain $$ J(\Psi) = \begin{pmatrix} c_0^2 & 0 & c_0 c_1 & 0\\ 0 & c_0^2 & 0 & -c_0 c_1 \\ c_0 c_1 & 0 & c_1^2 & 0\\ 0 & -c_0 c_1 & 0 & c_1^2 \end{pmatrix}. $$ This operator has rank 2, which means just 2 Kraus operators suffice. We can get them through a spectral decomposition of $J(\Psi)$. Specifically, we have $$ J(\Psi) = \begin{pmatrix} c_0\\ 0\\ c_1\\ 0 \end{pmatrix} \begin{pmatrix} c_0 & 0 & c_1 & 0 \end{pmatrix} + \begin{pmatrix} 0\\ c_0\\ 0\\ -c_1 \end{pmatrix} \begin{pmatrix} 0 & c_0 & 0 & -c_1 \end{pmatrix}, $$ and by "folding up" these vectors we get Kraus operators: $$ \Psi(X) = B_0 X B_0^{\dagger} + B_1 X B_1^{\dagger} $$ where $$ B_0 = \begin{pmatrix} c_0 & 0\\ c_1 & 0 \end{pmatrix} \quad\text{and}\quad B_1 = \begin{pmatrix} 0 & c_0 \\ 0 & -c_1 \end{pmatrix}. $$
I'll discuss a slightly different approach to obtain the same result given in the other answer.
You are given a completely positive quantum map in Kraus representation: some $\Phi:\mathrm L(\mathcal X)\to\mathrm L(\mathcal Y)$ with $$\Phi(X) = \sum_a A_a X A_a^\dagger, \qquad \forall X\in\mathrm L(\mathcal X).$$ Here $A_a\in\mathrm L(\mathcal X,\mathcal Y)$ are the Kraus operators of the map. Observe that you can always write a channel in its Stinespring representation as $\Phi(X)=\operatorname{Tr}_{\mathcal Z}(VXV^\dagger)$ for some isometry $V\in\mathrm U(\mathcal X,\mathcal Y\otimes\mathcal Z)$. Kraus and Stinespring dilations are tightly related via $A_a=(I\otimes\langle a|)V$ with $|a\rangle$ an orthonormal system for $\mathcal Z$ (more precisely, I should have said that given a channel corresponding to the isometry $V$, the set of operators $A_a$ thus defined gives a valid Kraus decomposition for $\Phi$, and vice versa given a Kraus decomposition the operator thus defined is an isometry). Note that different choices of orthonormal system $\{|a\rangle\}_a$ result in different Kraus decomposition, but same overall map.
In summary, we have $A_a=(I\otimes\langle a|)V$ for some isometry $V$. The complementary map of $\Phi$ is then the one whose Kraus operators are obtained "projecting on the other side" of $V$. Meaning $\tilde A_a\equiv(\langle a|\otimes I)V$. I would note that there might be some subtleties with this associated to the different dimensionality of $\mathcal Y$ and $\mathcal Z$, which should however disappear redefining things so that $\mathcal Y\simeq\mathcal X$ and choosing $\mathcal Z$ to have smallest required dimension (i.e. $\dim(\mathcal Z)=\operatorname{rank}(J(\Phi))$).
The intuition is pretty straightforward: if you understood $\Phi$ as evolution through some $V$ followed by ignoring part of the output, the complementary channel is the one corresponding to the same evolution through $V$, but instead ignoring the other (complementary!) part of the output.
Let's consider a few examples to concretise these arguments.
Let's start by considering the identity map $\Phi=\operatorname{Id}$ in a $d$-dimensional space, that is, $\Phi(X)=X$ for all $X\in\mathrm L(\mathbb{C}^d)$. Its Choi is $J(\operatorname{Id})=\mathbb{P}_m$, where $\mathbb{P}_m\equiv |m\rangle\!\langle m|$ and $|m\rangle\equiv \sum_{i=1}^d |i,i\rangle$. The Choi has unit rank, and therefore there is a unique choice of Kraus operators: the trivial one with $\Phi(X)=AXA^\dagger$, $A=I$. In this case there is also a trivial choice of dilation isometry $V$: just $V=I_d$. Or equivalently, you might write $V=I_d\otimes 1$, where $1$ is here the "vector" spanning the trivial one-dimensional space, which you'd then trace out in the formula. Things look somewhat weird because this would be a linear map $V:\mathbb{C}^d\to \mathbb{C}^d\otimes \mathbb{C}\simeq \mathbb{C}^d$.
For the complementary channel(s), we'd get $$\Phi^c(X)= \operatorname{tr}_1[VXV^\dagger] = \operatorname{tr}(X)\in\mathbb{C}.$$ In words, this is telling us that if all the information about the input state goes into one output, then the other output holds no information about the input. Note that you get essentially the same result using the other recipe: $$\Phi^c(X)= \sum_{ij} \operatorname{tr}(A_j^\dagger A_i X) |i\rangle\langle j|= \operatorname{tr}(X) |0\rangle\!\langle 0|,$$ with $|0\rangle$ the only spanning unit vector in the ancillary one-dimensional space.
We should however observe that the dilation used above is not unique. You can show in general that any pair of dilation isometries $V,V'$ are related as $V=(I\otimes U^T)V'$ where $U$ or $U^\dagger$ is an isometry. In this case, this translates into dilation isometries having the form $V=I_d\otimes |\psi\rangle$ for any state $|\psi\rangle$. The corresponding complementary channels then read $\Phi^c(X)=\operatorname{tr}(X) \mathbb{P}_\psi$. You can also get this result more directly observing that complementary channels are always connected via an isometric channel, see e.g. https://arxiv.org/abs/2011.04672, below Definition 4.5.
Let $\Phi(X)=WXW^\dagger$ be an isometric channel, with $W$ some isometry, and suppose $$\Phi:\operatorname{Lin}(\mathbb{C}^d)\to\operatorname{Lin}(\mathbb{C}^{d'}).$$ Similar reasoning as before tells you that dilation isometries have the form $V=W\otimes |\psi\rangle$, and the corresponding complementary channels thus are $$\Phi^c(X) = \operatorname{tr}_1[VXV^\dagger]=\operatorname{tr}(WXW^\dagger) \mathbb{P}_\psi = \operatorname{tr}(X) \mathbb{P}_\psi.$$
Consider now a dephasing channel: $$\Phi(\rho) = p \rho + (1-p) Z\rho Z, \quad p\in[0,1].$$ As discussed in this other answer, in the case of this being a qubit-channel, an isometric dilation is $$V = \begin{pmatrix} \sqrt p \,I \\ \sqrt{1-p} \,Z \end{pmatrix},$$ where each of the two blocks here is one Kraus operator. You can equivalently read this as saying that the dilated isometric evolution looks like $$|\psi\rangle\mapsto \sqrt p|\psi\rangle|0\rangle+\sqrt{1-p} (Z|\psi\rangle)|1\rangle.$$ The image of the complementary channel is therefore (at least) two-dimensional. We can then also compute it explicitly, getting $$\Phi^c(\rho) = p \langle I^\dagger I,\rho\rangle E_{00} + \sqrt{p(1-p)}\langle I^\dagger Z,\rho\rangle E_{01} \\ + \sqrt{p(1-p)}\langle Z^\dagger I,\rho\rangle E_{10} + (1-p)\langle Z^\dagger Z,\rho\rangle E_{11} \\ = \operatorname{tr}(\rho)\begin{pmatrix} p&0\\0&1-p\end{pmatrix} + \sqrt{p(1-p)} (\rho_{00}-\rho_{11}) X.$$ Note that in this case looking at the environment (i.e. the considering the complementary channel) doesn't reveal some of the information that was getting lost in the system, such as information about the coherence terms $\operatorname{tr}(X\rho)$. On the contrary, the environment alone also only has information about the population of the state (albeit in a somewhat degraded form). In this case, the "missing information" is encoded into the correlations between system and environment.