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.
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.
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.
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.