Group:Grad-student Theory Lunch
Title: Triangulation Graph Random Walk Problem
Speaker: Xiang Zhang,Hao Song Tsinghua university
Time: 2010-05-13 14:00-2010-05-13 13:30
Venue: FIT 1-222

Abstract:

Presenter: Hao Song

In this presentation, I will continue the investigation into the triangulation graph random walk problem.

1. Brief review of the conductance technique - a commonly used technique to prove mixing time upper bound

2. Method used in Michael Molloy et al.'s 1998 paper to prove a polynomial upper bound of the random walk mixing time on the triangulation graph of a convex polygon. The method involves proving the existence a big matching between an arbitrary subset of the whole triangulation set and its complement, which, in turn, gives a lower bound on conductance.

3. Some of my efforts to generalize the method, and the difficulty I'm trying to overcome.




Short Bio: