2010 Kyoto Prize Laureates

Basic Sciences

Mathematical Sciences(including Pure Mathematics)

László Lovász

/  Mathematician

1948 -

Professor, Eötvös Loránd University

Commemorative Lectures

A Fledgeling Subject Bridging Classical Theory and New Applications


11 /11 Thu

Place:Kyoto International Conference Center


Mathematical Development of Algorithm Science


11 /12 Fri

13:00 - 17:20

Place:Kyoto International Conference Center

Achievement Digest

Outstanding Contributions to Mathematical Sciences Based on Discrete Optimization Algorithms

Through his advanced research on discrete structures, Dr. Lovász has provided a link among various branches of mathematics in terms of algorithms, thereby influencing a broad spectrum of the mathematical sciences – including discrete mathematics, combinational optimization and theoretical computer science. In so doing, Dr. Lovász has made outstanding contributions to the advancement of both the academic and technological possibilities of the mathematical sciences.


Dr. László Lovász has made outstanding contributions to the advancement of both the academic and technological possibilities of the mathematical sciences. Through his advanced research on discrete structures he has provided a link among many branches of mathematics in terms of algorithms. Many of his concrete research results are presented in the form of elucidation of the properties of graphs and their algorithmic designs. However, his methodologies go beyond the framework of graph theory to exert significant influence on a broad spectrum of mathematical sciences, including discrete mathematics, combinational optimization and theoretical computer science.

In 1972 Dr. Lovász proved the weak perfect graph conjecture, a well-known open problem in graph theory. This was one of his early representative achievements. The methodology shown in the proof holds high value as a culmination of the paradigm of expressing discrete structures by systems of linear inequalities. In 1979 he succeeded in solving a famous and long-standing open problem on Shannon capacity in the field of information theory. In this work he introduced quadratic forms to express discrete structures. It served as the very first instance of semidefinite programming, which went on to become one of the central topics in mathematical optimization. By further advancing those pioneering achievements he played a role in the development of the geometric methodology of algorithms based on the ellipsoid method, which led to the solution of a major open problem on submodular function minimization. His contributions are significant in clarifying the deeper relationship between computation theory and optimization theory. Through the renowned Lovász local lemma, he provided a fundamental tool of probabilistic methods for the analysis of discrete structures. He also contributed to the creation of a framework for probabilistically checkable proofs, and to the construction of important algorithms such as the matroid matching algorithm and the basis reduction algorithm for integer lattices. The reduction algorithm, commonly known as the LLL algorithm, is one of the basic tools in the theory of cryptography.

Going back and forth between algorithm theory and its peripheral areas in various mathematical topics, Dr. Lovász elucidated the connection and interaction of diverse fields within the mathematical sciences.

For these reasons, the Inamori Foundation is pleased to present the 2010 Kyoto Prize in Basic Sciences to Dr. László Lovász.


Born in Budapest, Hungary
Dr. Rher. Nat., Eötvös Loránd University
Research Associate, Eötvös Loránd University
Docent, József Attila University
Dr. Math. Sci., Hungarian Academy of Sciences
Professor, József Attila University
Professor, Eötvös Loránd University
Professor, Yale University
Senior Researcher, Microsoft Research
Director, Mathematical Institute, Eötvös Loránd University
Selected Awards and Honors
George Pólya Prize, Society for Industrial and Applied Mathematics
Delbert Ray Fulkerson Prize, American Mathematical Society
Commander's Cross Order of Merit of the Republic of Hungary
Wolf Prize in Mathematics, The Wolf Foundation
Gödel Prize, Association for Computer Machinery and EuropeanAssociation for Theoretical Computer Science
Bolyai János Research Prize, Bolyai Prize Foundation
Széchenyi Grand Prize, The Government of the Republic of Hungary
European Academy of Arts, Sciences and Humanities, Hungarian Academy of Sciences, The London Mathematical Society, German Academy of Sciences Leopoldina, Russian Academy of Sciences, The Royal Netherlands Academy of Arts and Sciences, The Royal Swedish Academy of Sciences
Selected Publications
Normal hypergraphs and the perfect graph conjecture. Discrete Mathematics 2: 253-267, 1972.
Problems and results on 3-chromatic hypergraphs and some related questions (Erdős, P. and Lovász, L.). in Infinite and Finite Sets, North Holland, Amsterdam, 609-627, 1975.
On the Shannon capacity of graphs. IEEE Transactions on Information Society 25: 1-7, 1979.
The ellipsoid method and its consequences in combinatorial optimization (Grötschel , M., Lovász, L., and Schrijver, A). Combinatorica 1: 169-197, 1981.
Factoring polynomials with rational coefficients (Lenstra, A. K., Lenstra, H.W., and Lovász, L.). Mathematische Annalen 261: 515-534, 1982.
Interactive proofs and the hardness of approximating cliques (Feige, U., Goldwasser, S., Lovász, L., Safra, S., and Szegedy, M.). Journal of the ACM 43: 268-292, 1996.

Profile is at the time of the award.