[Busec] MSR theory colloquium: László Lovász
Sharon Goldberg
goldbe at cs.bu.edu
Wed Sep 7 12:21:28 EDT 2011
All, I'm heading to MSR this afternoon to go to this talk. Drop me a note
if you'd like to come with me. -Sharon
******************************************************************************************************************************
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
******************************************************************************************************************************
Abstract
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 engineering.
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.
Biography
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
https://lists.eecs.harvard.edu/mailman/listinfo/econcs-general
--
Sharon Goldberg
Computer Science, Boston University
http://www.cs.bu.edu/~goldbe
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://cs-mailman.bu.edu/pipermail/busec/attachments/20110907/fcbf517b/attachment.html
More information about the Busec
mailing list