Difficulty of finding collisions for two different CRHF Suppose that $\mathcal{H}$ is a family of collision resistant hash functions. Given $h$, which was chosen uniformly at random from $\mathcal{H}$, it is infeasible for a polynomial-time adversary to find collisions for $h$.

Now suppose that $h_1$ and $h_2$ are chosen uniformly at random from $\mathcal{H}$. Is it still infeasible for an adversary to find two elements $x_1$ and $x_2$ such that $$h_1(x_1)=h_2(x_2)?$$ 

Why?

Thanks!
To expand my comment into an answer. The answer to the question is: No, in general this not true. We will formally show the following: 


  If a family of collision resistant hash functions $\mathcal{H}$
   exists, then there exists a family of collision resistant hash
   functions $\mathcal{H}'$ such that for any $h'_i,h'_j \in
 \mathcal{H}'$ it is trivial to find $x_i,x_j$ such that
   $h'_i(x_i)=h'_j(x_j)$.


As mentioned in my comment, what we will do is construct $\mathcal{H}'$ in such a way that $h'_i(i)=0^n$ (where $n$ is the output length of functions in $\mathcal{H}$).
However, we need to be careful in how we do that. A naïve construction of $\mathcal{H}'$ could define for each $h_i \in \mathcal{H}$ a function
$$h_i'(x) := \begin{cases} 0^n &amp; \text{if } x=i\\h_i(x)&amp;\text{otherwise} \end{cases} $$
However, this new family would not necessarily be collision resistant. If for example $\mathcal{H}$ was a family of functions where each function already mapped $0^n$ to $0^n$ we would have introduced a new easily found collision. 

So we need to be careful to ensure that any collision in our new function corresponds to a collision in the original function. To do that we define $\mathcal{H}'$ as follows. For each index $i$ we define
$$h'_i(x) := h_i(x)\oplus h_i(i).$$

It is actually easy to see that collision resistance is preserved under this modification.

Let $\mathcal{A}$ be an arbitrary PPT adversary against the collision resistance of $\mathcal{H}'$. We observe that for any $x_1,x_2$ that $\mathcal{A}$ outputs in response to input $i$, it holds that 
\begin{align}
&amp;h'_i(x_1) = h'_i(x_2)\\
\iff&amp; h_i(x_1)\oplus h_i(i) = h_i(x_2)\oplus h_i(i)\\
\iff&amp; h_i(x_1) = h_i(x_2)
\end{align}

Therefore it holds that
$$\Pr_i[(x_1,x_2)\gets\mathcal{A}(i):h'_i(x_1) = h'_i(x_2)] = \Pr_i[(x_1,x_2)\gets\mathcal{A}(i):h_i(x_1) = h_i(x_2)]$$
the latter of which is known to be negligible by our premise that $\mathcal{H}$ is collision resistant.

However, it is also easy to see that for any $i,j$ it is trivial to find $x_i,x_j$ such that $h'_i(x_i)=h'_j(x_j)$. An attacker given indices $i,j$ would simply output $i,j$ and since by definition of $\mathcal{H}'$ it holds that

$$h'_i(i) = h_i(i) \oplus h_i(i) = 0^n$$
and
$$h'_j(j) = h_j(j) \oplus h_j(j) = 0^n$$
$\mathcal{A}$ would be succesfull with probability $1$.