Distinguished Speaker Series
László Lovász
Eötvös Loránd University
Hyperfiniteness, a decomposition principle for networks
Tue
Apr 3, 2018
Download TALK slides
12:30 pm
177 Huntington Ave
11th floor
ADD to calendar

Decomposition of graphs is an important tool for the design ofalgorithms as well as for understanding their structure.Hyperfiniteness means that the graph can be decomposed into pieces ofbounded size by removing an arbitrarily small fraction of the edges.This property, which can be defined for a family of finite graphs,but also for graph-limits with bounded degree called "graphings", isvery useful in designing local algorithms for such graphs. But theoptimal decomposition is difficult to compute. We show how methodsfrom combinatorial optimization, namely linear relaxation, can beused to prove basic properties of hyperfiniteness, and also to obtaina decomposition that is almost optimal.

about the speaker
László Lovász was born on March 9, 1948 in Budapest, Hungary. He is married, has 4 children. He obtained his doctoral degree in mathematics from the Eötvös Loránd University, in Budapest, Hungary in 1971. He is a member of the Hungarian Academy of Sciences, the US National Academy of Sciences and several other Academies. He held the Chair of Geometry at the University of Szeged (1975-1982) and the Chair of Computer Science at the Eötvös Loránd University (Budapest, 1983-1993). He was A.D. White Professor-at-Large at Cornell University (1982-1987), Professor of Mathematics and Computer Science at Yale University (1993-1999), Senior/Principal Researcher at Microsoft Research (1999-2006), Director of the Mathematical Institute of the Eötvös Loránd University (2006-2011), and since 2014, he is the President of the Hungarian Academy of Sciences. His awards include the George Polya Prize (1979), the Ray D.Fulkerson Prize (1982), the Brouwer Medal of the Dutch Mathematical Society (1993), the Wolf Prize (1999), the Knuth Prize (1999), the Gödel Prize (2001), and the Kyoto Prize (2010). He is editor-in-chief of Combinatorica and editor of 12 other Journals. His field of research is discrete mathematics, in particular its applications to the theory of algorithms and the theory of computing, discrete probability, and its interactions with classical mathematics. He wrote 5 research monographs and 4 textbooks, and over 250 research papers.

No upcoming events

Thank you! You have been added to our email list.

Oops! Something went wrong while submitting the form