Yangtze Microsoft Colloquium on Theoretical Computer Science

Up coming seminar. (See previous seminars: Dec. 23, 2011, Nov. 11, 2011,   Oct. 21, 2011,  Sep. 14, 2011,  Jun. 29, 2011,  May. 26, 2011,   Apr. 15, 2011,  Mar. 31, 2011,  Feb. 22, 2011,  Jan. 18, 2011,   Jan. 11, 2011

Date: Tuesday, Jan. 10th , 2012

Place: Room 601, Pao Yue-Kong Library,Shanghai Jiao Tong University



11:00- 12:00

Title: Distributed Streaming

Speaker: Qin Zhang (Aarhus University, Denmark)

Abstract: In this talk we will discuss the distributed streaming model. In this model, we have k sites, each receiving a stream of elements over time. There is a designated coordinator who would like to track, that is, maintain continuously at all times, some function f of all the elements received from the k sites. There is a two-way communication channel between each site and the coordinator, and the goal is to track f with minimum communication. This model is motivated by applications in distributed databases, network monitoring and sensor networks.

In this talk we will first introduce the model and review the existing results in this model, and then focus on one particular problem: tracking the number of distinct elements (F0). We will discuss both upper bound and lower bound for the F0 problem, so as to give an example for designing algorithms / analyzing complexities in the distributed streaming model.

Lunch (12:00-2:00)


Title: Research ideas in spectral methods for community detection

Speaker: John Hopcroft (Cornell University)

Abstract: This talk will explore some problems having to do with spectral methods for community detection. Spectral methods are well understood for partitioning the vertices of a graph into disjoint classes. However, communities in social networks are not likely to be disjoint and so the techniques need to be extended. The work relates to research in sparse vectors and with the use of random walk techniques to find communities in time proportional to the community size rather than the size of the entire graph.

3:00 -3:30 Tea Break


Title:  Streaming / communication complexity lower bound for some graph and linear algebra problems

Speaker: Xiaoming Sun (Institute of Computing Technology, CAS)

Abstract: In this talk we consider the streaming /communication complexity lower bound for some graph and linear algebra problems including: approximate the clique number, decide the bipartiteness of a graph, and compute the rank/det of a matrix etc. We get some new randomized /quantum lower bound for these problems. The proof of these bound involved the using of reduction from Set-Disjointness problem, the approximate norm method, Fourier analysis on matrix, and Szemeredi regular lemma.

This talk is based on the joint work with Chenggu Wang, Wei Yu, Mario Szegedy and Halldorsson.