Wolf Prize Laureate in Mathematics 1999
Affiliation at the time of the award:
Yale University, USA
Eotvos University, Hungary
“for his outstanding contributions to combinatorics, theoretical computer science and combinatorial optimization”.
Professor Laszlo Lovasz has obtained ground breaking results in discrete mathematics which have had very significant applications to other areas of pure and applied mathematics as well as to theoretical computer science. He solved several outstanding problems including the perfect graph conjecture, Kneser’s conjecture and the determination of the Shannon capacity of the pentagon, by introducing deep mathematical methods relying on geometric, polyhedral and topological techniques. His algorithmic ideas, including applications of the ellipsoid method in combinatorial optimization, the lattice basis reduction algorithm, the matroid parity algorithm and the improved procedures for volume computation, all had profound influence on theoretical computer science. He also contributed to the PCP characterization of NP land its connection to the hardness of approximation. His “Local Lemma” is one of the main early results in the development of the probabilistic method. His comprehensive books and fascinating lectures have stimulated mathematical research around the world.