Hyperfiniteness, a decomposition principle for networks
Distinguished Speaker Series
Past Talk
László Lovász
Eötvös Loránd University
Apr 3, 2018
Watch video
12:30 pm
177 Huntington Ave
Join Talk (Zoom)
11th floor

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.