פרופ' לזלו לובס מאוניברסיטת לורנד, בודפסט, הונגריה, יהיה אורח מיוחד בפקולטה למדעי המחשב ויתן סדרת הרצאות כדלהלן:
הרצאה מס' 1:
Large Networks, Graph Limits, And Why Are They Useful
יום שלישי, 30 באפריל 2013, 14:3--15:30, טאוב 337
ההרצאה מיועדת לסגל וסטודנטים כמו גם לקהל רגיל
If you have a very large network (which may be deterministic or the
result of some random procedure), we may want to approximate it by a
smaller object, or by an infinite (analytic) object. The former question
is related to Szemer\'edi's Regularity Lemma and its variants, the
latter, to "graph limits". A theory of convergent graph sequences and
their limits has been worked out by Benjamini and Schramm (for graphs
with bounded degree) and by Borgs, Chayes, Lov\'asz, S\'os, Szegedy and
Vesztergombi (for dense graphs). Focusing on the dense case, I will
describe the motivation for graph limit theory and some basic facts.
הרצאה מס' 2:
Limits of Dense Graphs: Algorithms And Extremal Graph Theory
יום רביעי, 1 במאי, 2013, 13:30--14:30, טאוב 337
ההרצאה מיועדת לבעלי נטייה למתמטיקה
Applications of graph limit theory to algorithmic problems present novel
challenges; some of the classical algorithmic problems must be
rephrased, and a new kind of complexity theory emerges. Much of this has
been worked out in the theory of "Graph Property Testing" in computer
science, where we assume that information about such graphs is obtained
by an appropriate sampling procedure. Graph limits offer a new
perspective on this field, along with some new results.
Many questions in extremal graph theory can be phrased like this: what
is the maximum of a certain linear combination of densities of given
graphs in any graph G? Answers to such questions are often quite
difficult. Graph limits make it possible to pose and in some cases
answer some general questions about extremal graphs: Which inequalities
between subgraph densities are valid? Can all valid inequalities be
proved using just Cauchy-Schwarz? Is there always an extremal graph?
Which graphs are extremal?
הרצאה מס' 3:
Limits of Sparse Graphs: Distributed Algorithms And Group Theory
יום חמישי, 2 במאי, 2013, 14:30--15:30, טאוב 337
ההרצאה מיועדת לבעלי נטיה למתמטיקה
The limit theory of bounded-degree graphs is very interesting, but
substantially more challenging than the dense theory. Limit objects can
be defined in more than one sense; an interesting class of infinite
graphs, which are called graphings and have been known from group theory
and ergodic theory for a while, can be used to describe limit objects.
Algorithmic questions in this theory are closely related to distributed
computing in constant time.
László Lovász, born in 1948 in Budapest, is a Hungarian-American mathematician, best known for his work in combinatorics, combinatorial optimization, graph theory and their impact on computer science, for which he was awarded the Wolf Prize and the Knuth Prize in 1999, and the Kyoto Prize in 2010. He received the Fulkerson Prize twice (1982, 2012), Hungary's Széchenyi Grand Prize (2008), Bolyai prize (2007), Gödel Prize (2001).
Lovász received his Candidate of Sciences degree in 1970 at Hungarian Academy of Sciences. His advisor was Tibor Gallai. Until 1975, Lovász worked at the Eötvös University, between 1975-1982 he led the Department of Geometry at the University of Szeged.
In 1982 he returned to the Eötvös University, where he created the Department of Computer Science.
Lovász was a professor at Yale University during the 1990s and was a collaborative member of the Microsoft Research Center until 2006.
He returned to Eötvös Loránd University, Budapest, where he was the director of the Mathematical Institute (2006-2011). He served as president of the International Mathematical Union between January 1, 2007 and December 31, 2010.
: Avi Wigderson interviews László Lovász.