a partition $U_1$, $U_2$ such that $U_1$, $U_2$ are $\rho'$-components,

and in the case of (ii) identifies the partition $U_1, U_2$. We call this Algorithm 1.

\[th:alg2\] For each fixed choice of parameters $1/n_0 \ll \rho \ll \rho'\ll\alpha <1$ there is a polynomial time algorithm that does the following. Given a $D$-regular, $n$-vertex graph $G=(V,E)$ and $U \subseteq V$ as input, where $D \geq \alpha n$, $n \geq n_0$, and $G[U]$ is a $\rho$-component of $G$, the algorithm determines that either

1.  $G[U]$ is not $\rho$-close to bipartite, or

2.  $G[U]$ is $\rho'$-close to bipartite,

and in the case of (ii) identifies the corresponding bipartition. We call this Algorithm 2.

\[th:alg3\] For each fixed choice of parameters $1/n_0 \ll \rho \ll \nu  \ll \rho'\ll \tau \ll \alpha < 1$ there is a polynomial-time algorithm that does the following. Given a a $D$-regular, $n$-vertex graph $G=(V,E)$ and $U \subseteq V$ as input, where $D \geq \alpha n$, $n \geq n_0$, and $G[U]$ is $\rho$-close to bipartite with bipartition $A,B$, the algorithm determines that either

1.  $G[U]$ is a bipartite robust $(\nu,\tau)$-expander with bipartition $A,B$, or

2.  $U$ has a partition $U_1$, $U_2$ such that $G[U_1]$, $G[U_2]$ are $\rho'$-components,

and in the 