### Abstract

Given a background graph with n vertices, the binary censored block model assumes that vertices are partitioned into two clusters, and every edge is labeled independently at random with labels drawn from Bern(1 - ϵ) if two endpoints are in the same cluster, or from Bern(ϵ) otherwise, where ϵ [0; 1/2] is a fixed constant. For Erd's-Rényi graphs with edge probability p = a log n/n and fixed a, we show that the semidefinite programming relaxation of the maximum likelihood estimator achieves the optimal threshold equation for exactly recovering the partition from the labeled graph with probability tending to one as n → ∞. For random regular graphs with degree scaling as a log n, we show that the semidefinite programming relaxation also achieves the optimal recovery threshold aD(Bern(1/2)Bern(ϵ)) > 1, where D denotes the Kullback-Leibler divergence.

Original language | English (US) |
---|---|

Title of host publication | ITW 2015 - 2015 IEEE Information Theory Workshop |

Publisher | Institute of Electrical and Electronics Engineers Inc. |

Pages | 99-103 |

Number of pages | 5 |

ISBN (Electronic) | 9781467378529 |

DOIs | |

State | Published - Dec 17 2015 |

Event | IEEE Information Theory Workshop, ITW 2015 - Jeju Island, Korea, Republic of Duration: Oct 11 2015 → Oct 15 2015 |

### Publication series

Name | ITW 2015 - 2015 IEEE Information Theory Workshop |
---|

### Other

Other | IEEE Information Theory Workshop, ITW 2015 |
---|---|

Country | Korea, Republic of |

City | Jeju Island |

Period | 10/11/15 → 10/15/15 |

### Fingerprint

### ASJC Scopus subject areas

- Information Systems

### Cite this

*ITW 2015 - 2015 IEEE Information Theory Workshop*(pp. 99-103). [7360742] (ITW 2015 - 2015 IEEE Information Theory Workshop). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ITWF.2015.7360742