NP-hardness of approximating Uniform Sparsest Cut within every constant factor
Theorem 1.1: for every fixed there is a polynomial-time reduction from 3SAT producing uniform-demand instances with a multiplicative gap , so approximating Uniform Sparsest Cut within any constant factor is NP-hard. The constants and exponents of the reduction depend on . It does not give a superconstant (for instance -type) hardness factor, does not address Balanced Separator directly, an…