  We consider the problem of determining the maximal $\alpha \in (0,1]$ such
that every matching $M$ of size $k$ (or at most $k$) in a bipartite graph $G$
contains an induced matching of size at least $\alpha |M|$. This measure was
recently introduced in Alon et al. (NIPS 2018) and is motivated by
connectionist models of cognition as well as modeling interference in wireless
and communication networks.
  We prove various hardness results for computing $\alpha$ either exactly or
approximately. En route to our results, we also consider the maximum connected
matching problem: determining the largest matching $N$ in a graph $G$ such that
every two edges in $N$ are connected by an edge. We prove a nearly optimal
$n^{1-\epsilon}$ hardness of approximation result (under randomized reductions)
for connected matching in bipartite graphs (with both sides of cardinality
$n$). Towards this end we define bipartite half-covers: A new combinatorial
object that may be of independent interest. To the best of our knowledge, the
best previous hardness result for the connected matching problem was some
constant $\beta>1$.
  Finally, we demonstrate the existence of bipartite graphs with $n$ vertices
on each side of average degree $d$, that achieve $\alpha=1/2-\epsilon$ for
matchings of size sufficiently smaller than $n/poly(d)$. This nearly matches
the trivial upper bound of $1/2$ on $\alpha$ which holds for any graph
containing a path of length 3.
