演讲人： Mario Szegedy 罗格斯大学
时间： 2010-10-12 14:00-2010-10-12 15:00
地点：FIT 1-222
内容：

In the semi-streaming model we receive the edges of the input graph in a stream. The goal is to compute or approximate a graph property in space nearly linear in the number of nodes. We show this is not possible for the problem of the maximum independent set. (Joint with Magnus Halldorsson)

个人简介:

Mario Szegedy is a Hungarian-born computer scientist, professor of computer science at Rutgers University. He received his Ph.D. in computer science from the University of Chicago. Szegedy's research areas include complexity theory, combinatorics and quantum computing. He was awarded the Gödel Prize twice in 2001 and 2005 for his work on probabilistically checkable proofs and on the space complexity of approximating the frequency moments in streamed data.