Graph Limits in Computer Science: Gabor Lippner, Harvard University (CS Colloquium)

2:00 pm on Wednesday, November 20, 2013
4:00 pm on Wednesday, November 20, 2013
MCS 148
Abstract: In the past two decades, the emergence of very large datasets - and networks in particular - posed new challenges for both computer science and graph theory. What can we compute in less than linear time? Is there hope for algorithms whose running time does not depend on the size of the data? Is there a "good" way to represent large graphs? In this survey talk I will give an introduction to theory of graph limits (approximating large graphs with functions) and outline its connections to constant time algorithms in order to answer these questions.