[Busec] MSR theory colloquium next Wednesday: László Lovász

Sharon Goldberg goldbe at cs.bu.edu
Fri Sep 2 11:52:27 EDT 2011

Looks really interesting; I'll probably go.

WHO:  László Lovász
AFFILIATION:  Department of Computer Science of the Eötvös Loránd
University in Budapest, Hungary
TITLE:  The mathematical challenge of large networks
HOST:  Jennifer Chayes
WHEN:   Wednesday September 7th
WHERE:   Microsoft Conference Center located at One Memorial Drive,
First Floor, Cambridge, MA
TIME:  4:00 PM – 5:30 PM

It is becoming more and more clear that many of the most exciting
structures of our world can be described as large networks. The
internet is perhaps the foremost example, modeled by different
networks (the physical internet, a network of devices; the world wide
web, a network of webpages and hyperlinks). Various social networks,
several of them created by the internet, are studied by sociologist,
historians, epidemiologists, and economists. Huge networks arise in
biology (from ecological networks to the brain), physics, and
These networks pose exciting and challenging problems for the
mathematician: these networks are never completely known, and  indeed
often not even completely defined.
At any time, we can only have partial information about them, through
sampling locally, or  observing the behavior of some global process.
The approach to the study of such networks includes finding  procedures (usually
randomized) that produce networks with similar behavior; this relates
to the theory of random graphs and randomly growing graphs, and the
theory of „Property Testing” in computer science. The  methods involve
defining a "distance" between two large graphs,  defining when a
growing sequence of graphs is convergent, and  assigning limit objects
to such sequences.
The limit theory allows us to answer some basic questions both in
theory and practice. For example, in extremal graph theory: Which
inequalities between subgraph densities are valid? Can these be proved
using just Cauchy-Schwarz? is there always and extremal graph, and
what is the possible structure of these?
The limit theory has been developed by Borgs, Chayes, Lovasz, Sos,
Szegedy and Vesztergombi in the dense case, and by Aldous, Benjamini,
Schramm, Elek and others in the sparse case.

I am a Professor in the Department of Computer Science of the Eötvös
Loránd University in Budapest, Hungary.
My research topics: Combinatorial optimization, algorithms,
complexity, graph theory, random walks.

Econcs-general mailing list
Econcs-general at eecs.harvard.edu

Sharon Goldberg
Computer Science, Boston University

More information about the Busec mailing list