Abstract:
|
Semidefinite programming (SDP) is one of the most powerful tools to design efficient estimation algorithms. I will discuss SDP relaxations to several fundamental problems in graph estimation, including community detection, the hidden clique problem and the hidden subgraph problem. It appears that these approaches undergo sharp phase transitions depending on the model parameters. I will present examples in which this phase transition can be characterized precisely.
|