Assume that X is a connected \((p+1)\) -regular undirected graph of finite order n. Let A denote the adjacency matrix of X. Let \(\lambda _1=p+1>\lambda _2\ge \lambda _3\ge \ldots \ge \lambda _n\) denote the eigenvalues of A. By Cheeger’s inequality and Alon–Boppana theorem, the edge expansion and spectral expansion of X are quite high if \(\begin{aligned} \mu (X)=p^{-\frac{1}{2}} \max _{2\le i\le n}|\lambda _i| \end{aligned}\) is close to 2 when n is large enough. The graph X is a good expander if the parameter p is low and the edge expansion and spectral expansion are high. The good expanders have significant applications to networks, error-correcting codes and probabilistic algorithms. In this paper, with the inputs A and a real number \(\varepsilon >0\) we design an algorithm to estimate whether \(\mu (X)\le 2+\varepsilon \) in \(O(n^\omega \log \log _{1+\varepsilon } n )\) time, where \(\omega \) is the exponent of matrix multiplication.
