讨论组:研究生会议
标题:Communication Complexity Lower Bound of Determinant,Minimum rOuting Cost Connect
演讲人: 吴辰晔,王晨谷,张家琳 清华大学
时间: 2010-04-22 12:00-2010-04-22 13:30
地点:FIT 1-222

内容:

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.




人物介绍: