# Sparse-cut approximation for well connected graphs

Theorem: For any graph $G=(V,E)$, there is a polynomial time algorithm that finds a cut $S \subseteq V$ with conductance at most $\sqrt{2\big(1 − \lambda(G)\big)}$.

If I understand UGC correctly, the above result is tight for general graph under UGC.

Question: Can we obtain a better approximation if we have the promise - $mincut(G) = O(\log n )$?

• what is $\lambda$? what is conductance? May 21 '17 at 22:31
• @Saeed: The 2nd largest value of the normalized Adjaceny matrix. May 22 '17 at 6:03