Group:Grad-student Theory Lunch
Title: Communication Complexity Lower Bound of Determinant,Minimum rOuting Cost Connect
Speaker: Chenye Wu, Chengu Wang, Jialin Zhang Tsinghua university
Time: 2010-04-22 12:00-2010-04-22 13:30
Venue: FIT 1-222

Abstract:

Topic 1: Communication Complexity Lower Bound of Determinant

Alice and Bob take n/2 vectors in n dimentional boolean space respectively. They want to compute wheather the n vectors are linear dependent. J. I. Chu and G. Schnitger show that deterministic lower bound is \Omega(n^2) by counting the number of monochromatic rectangles. We can get the same 1-sided error lower bound easily. And we guess that the randomized lower bound is \Omega(n^2) as well.

Topic 2: Minimum rOuting Cost Connected Dominating Set in Unit Disk Graph

Between any two nodes in a network, there exists at least one shortest path, all of whose intermediate nodes should be included in the special CDS, named Minimum rOuting Cost CDS (MOC-CDS). Therefore, routing by MOC-CDS can guarantee that each routing path between any pair of nodes is also the shortest path in the network. Prof. Du gives a tight bound on this general problem. And he asks the special case that the network is a unit disk graph.




Short Bio: