  In this paper, we study the complexity of solving generic over-determined
bilinear systems over a finite field $\mathbb{F}$. Given a generic bilinear
sequence $B \in \mathbb{F}[\mathbf{x},\mathbf{y}]$, with respect to a partition
of variables $\mathbf{x}$, $\mathbf{y}$, we show that, the solutions of the
system $B= \mathbf{0}$ can be efficiently found on the
$\mathbb{F}[\mathbf{y}]$-module generated by $B$. Following this observation,
we propose three variations of Gr\"obner basis algorithms, that only involve
multiplication by monomials in they-variables, namely, $\mathbf{y}$-XL, based
on the XL algorithm, $\mathbf{y}$-MLX, based on the mutant XL algorithm, and
$\mathbf{y}$-HXL, basedon a hybrid approach. We define notions of regularity
for over-determined bilinear systems,that capture the idea of genericity, and
we develop the necessary theoretical tools to estimate the complexity of the
algorithms for such sequences. We also present extensive experimental results,
testing our conjecture, verifying our results, and comparing the complexity of
the various methods.
