Approximating Dasgupta Cost in Sublinear Time from a Few Random Seeds

Michael Kapralov, Akash Kumar, Silvio Lattanzi +2

Testing graph cluster structure has been a central object of study in property testing since the foundational work of Goldreich and Ron [STOC'96] on expansion testing, i.e. the pro…