Noisy graph isomorphismSpeaker: Zhixian
Title: Noisy graph isomorphism
Date: 02 Apr 2018 5:30pm-7:00pm
Location: Pierce 320
Food: Chinese food
Abstract: We studied graph isomorphism problem in noisy sparse graph setting. Both polynomial time distinguish algorithm and quasi-polynomial time recovery algorithm are provided. The essence of the algorithm is to use strictly balance property to make graph counts look like independent.