Guy Bresler, MIT

Computational Universality for Community Detection
Date
Dec 13, 2017, 3:00 pm4:00 pm
Location
214 - Fine Hall
Event Description

Abstract: We consider the problem of detecting existence of a single hidden community of size K in a graph where edges between members of the community have label X drawn i.i.d. according to P and all other edges have labels drawn i.i.d. according to Q. We show that for a broad class of distributions P and Q both the information limits and the computational hardness (based on planted clique) are determined by the KL-divergence between P and Q. We additionally show how to reduce general P and Q to the case P = Ber(p) and Q = Ber(q) and vice versa, while losing only logarithmic factors in the divergence, giving a direct approximate computational equivalence. This is joint work with Matthew Brennan and Wasim Huleihel.

Event Category
Probability Seminar