  We prove that any semi-streaming algorithm for $(1-\epsilon)$-approximation
of maximum bipartite matching requires \[
\Omega(\frac{\log{(1/\epsilon)}}{{\log{(1/\beta)}}}) \] passes, where $\beta
\in (0,1)$ is the largest parameter so that an $n$-vertex graph with
$n^{\beta}$ edge-disjoint induced matchings of size $\Theta(n)$ exist (such
graphs are referred to as RS graphs). Currently, it is known that \[
\Omega(\frac{1}{\log\log{n}}) \leqslant \beta \leqslant
1-\Theta(\frac{\log^*{n}}{{\log{n}}}) \] and closing this huge gap between
upper and lower bounds has remained a notoriously difficult problem in
combinatorics.
  Under the plausible hypothesis that $\beta = \Omega(1)$, our lower bound
result provides the first pass-approximation lower bound for (small) constant
approximation of matchings in the semi-streaming model, a longstanding open
question in the graph streaming literature.
  Our techniques are based on analyzing communication protocols for compressing
(hidden) permutations. Prior work in this context relied on reducing such
problems to Boolean domain and analyzing them via tools like XOR Lemmas and
Fourier analysis on Boolean hypercube. In contrast, our main technical
contribution is a hardness amplification result for permutations through
concatenation in place of prior XOR Lemmas. This result is proven by analyzing
permutations directly via simple tools from group representation theory
combined with detailed information-theoretic arguments, and can be of
independent interest.
