2010Basic SciencesMathematical Sciences (including Pure Mathematics)
László Lovász photo

László Lovász

  • Hungary, U.S.A. / March 9, 1948
  • Mathematician
  • Professor, Eötvös Loránd University

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.

Profile

Brief Biography

1948
Born in Budapest, Hungary
1971
Dr. Rher. Nat., Eötvös Loránd University
1971
Research Associate, Eötvös Loránd University
1975
Docent, József Attila University
1977
Dr. Math. Sci., Hungarian Academy of Sciences
1978
Professor, József Attila University
1983
Professor, Eötvös Loránd University
1993
Professor, Yale University
1999
Senior Researcher, Microsoft Research
2006
Director, Mathematical Institute, Eötvös Loránd University

Selected Awards and Honors

1979
George Pólya Prize, Society for Industrial and Applied Mathematics
1982
Delbert Ray Fulkerson Prize, American Mathematical Society
1998
Commander's Cross Order of Merit of the Republic of Hungary
1999
Wolf Prize in Mathematics, The Wolf Foundation
2001
Gödel Prize, Association for Computer Machinery and European
Association for Theoretical Computer Science
2007
Bolyai János Research Prize, Bolyai Prize Foundation
2008
Széchenyi Grand Prize, The Government of the Republic of Hungary
Members:
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

1972

Normal hypergraphs and the perfect graph conjecture. Discrete Mathematics 2: 253-267, 1972.

1975

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.

1979

On the Shannon capacity of graphs. IEEE Transactions on Information Society 25: 1-7, 1979.

1981

The ellipsoid method and its consequences in combinatorial optimization (Grötschel , M., Lovász, L., and Schrijver, A). Combinatorica 1: 169-197, 1981.

1982

Factoring polynomials with rational coefficients (Lenstra, A. K., Lenstra, H.W., and Lovász, L.). Mathematische Annalen 261: 515-534, 1982.

1996

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.

Citation

Outstanding Contributions to Mathematical Sciences Based on Discrete Optimization Algorithms

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.

Lecture

Abstract of the Lecture

Abstract of the Commemorative lecture A Fledgeling Subject Bridging Classical Theory and New Applications

I was introduced to my main research topic of graph theory in high school. I was lucky enough to be enrolled in a new specialized high school class for mathematics. Not only did I meet many outstanding students there (including my wife), but the famous mathematician Paul Erdős visited the school several times. He gave the students unsolved problems, one or two of which I could solve; so started my lifelong commitment to graph theory and to mathematical research. In those days, graph theory was still quite isolated from “mainstream” mathematics, and later I was often advised by older mathematicians to do something more serious instead. But for me, the novelty of the subject and its potential applications were fascinating.

In the last years of my studies, I got interested in the strong connection between operations research and graph theory. I solved a problem about perfect graphs, and the method of solution turned out to have interesting consequences in integer programming and through this, to polyhedra. I have found repeatedly that this connection between graph theory, optimization, and geometry is most fruitful.

Shortly after this, I learned about the new theory of algorithmic complexity, which had a lot of consequences in graph theory. This allowed me to be a witness (and a bit, a participant) of the fascinating co-development of the theory of computing and its mathematical basis, discrete mathematics (which includes graph theory).

Graph theory also has connections in the opposite direction, to classical mathematics, and I got fascinated with the question of applying such methods to solve graph-theoretical problems. Algebra, topology, geometry and probability theory are among those areas which can be applied in graph theory in interesting ways.

More recently, I got interested in the theory of very large networks (like the internet). This gives another new twist to graph theory, and further areas of classical mathematics turn out to be needed here. I have to re-learn areas that I last met when I was a student, I enjoy this enormously.

[Read More]
Full Text(PDF)
Workshop

Workshop

Mathematical Development of Algorithm Science

date
Friday, November 12, 2010
palce
Kyoto International Conference Center
Kazuo Murota
[Member, Kyoto Prize Selection Committee; Professor, Graduate School of Information Science and Technology, The University of Tokyo]
Organized by Inamori Foundation
Supported by Kyoto Prefectural Government, Kyoto City Government, and NHK
With the cooperation of Information Processing Society of Japan, The Institute of Electronics, Information and Communication Engineers, The Japan Society for Industrial and Applied Mathematics, The Mathematical Society of Japan, The Operations Research Society of Japan

Program

13:00
Opening Address Heisuke Hironaka [Chairman, Kyoto Prize Committee; Professor Emeritus, Kyoto University]
Introduction of Laureate Hiroshi Imai [Member, Kyoto Prize Selection Committee; Professor, Graduate School of Information Science and Technology, The University of Tokyo]
Laureate Lecture László Lovász (Laureate in Basic Sciences)
“The Mathematical Challenge of Very Large Networks”
Lecture Takeshi Tokuyama [Professor, Graduate School of Information Sciences, Tohoku University]
“Combinatorial Geometry: Mathematics for Geometric Data Processing”
Lecture Osamu Watanabe [Professor, Graduate School of Information Science and Technology, Tokyo Institute of Technology]
“CompView and the Lovász Local Lemma”
Lecture Satoru Iwata [Professor, Research Institute for Mathematical Sciences, Kyoto University]
“Convexity in Combinatorial Optimization”
Lecture Ken-ichi Kawarabayashi [Professor, National Institute of Informatics]
“Structure Theorems and Decomposition Theorems in Graph Theory”
17:20
Closing
PAGETOP