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

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

### Selected Awards and Honors

### Selected Publications

- 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

- 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

- 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

### Program

- 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

Links

N/A