Born: 9 March 1948 in Budapest, Hungary

Laszlo Lovász was educated in Budapest where he showed outstanding ability in mathematics at secondary school. When he was fourteen years old, Lovász came across an article by Paul Erdős in the Mathematical and Physical Journal for Secondary Schools (1962) and was so enchanted that he read it "at least twenty times". In the following year he was able to meet his mathematical hero in person [3]:-

I had the great fortune to meet Paul Erdős as a high school student in 1963. In those days the cold war was quieting down a little, and he began to visit Hungary more and more often. ... It is an understatement to say that I have learned a lot from him, not only mathematics in the technical sense, and not even only elements of the fine art of problem solving, but also his way of pursuing knowledge: complete openness in problems and partial results, which necessarily leads to collaboration and a wider perspective.

Inspired by Erdős, Lovász won gold medals in the International Mathematical Olympiad competition in each of the three years 1964, 1965 and 1966. Lovász's first paper On graphs not containing independent circuits was published in 1965 when he was seventeen years old. In this paper he classified graphs in which any two circuits have a common node. This was not an isolated paper for, in the next couple of years, he published On decomposition of graphs (1966), Operations with structures (1967), Über die starke Multiplikation von geordneten Graphen (1967), On connected sets of points (1967), and On chromatic number of finite set-systems (1968). Frank Harary describes this last mentioned paper as follows:-

P Erdős proved by probabilistic methods [in 1959] that for any positive integers n, g ≥ 3, there exists a graph with chromatic number n and girth ≥ g, but was unable to construct such graphs. By generalizing the question from graphs to finite set-systems, the author succeeds in obtaining such a construction for graphs.

After graduating from high school, Lovász studied at Eötvös Loránd University in Budapest and he was awarded a Candidate Degree of Mathematical Science (C.Sc.) in 1970 by the Hungarian Academy of Sciences in Budapest. At this time the Candidate Degree awarded by the Hungarian Academy of Sciences was considered a higher degree than a doctorate awarded by a university so it may appear puzzling that he received this degree first. The reason was that university regulations did not allowed a student to apply for a Ph.D. with results achieved during their undergraduate years. No such rules existed in the Academy of Sciences, however, because when the rules were drawn up it was assumed that an undergraduate would never be able to produce research of sufficient depth to entitle him to apply for the C.Sc. degree. Remarkably, Lovász had fifteen papers in print by the time he was awarded his Candidate Degree in 1970. Before the award of any degree, he had lectured at several international conferences and published papers in conference proceedings such as: Theory of graphs held in Tihany, on the northern shore of Lake Balaton, in Hungary in September 1966; Beiträge zur Graphentheorie held in Manebach, Germany in May 1967; Combinatorial Structures and their Applications held at the University of Calgary in Canada in 1969; and Combinatorial Theory and its Applications held in Balatonfüred on the northern shore of Lake Balaton, in Hungary in 1969.

For his outstanding achievements, Lovász received the Grünwald Géza Prize from the Bolyai Society in 1970. In the following year he was awarded a doctorate (Dr.Rher.Nat.) from Eötvös Loránd University in Budapest for his thesis Factors of Graphs. His thesis advisor was Tibor Gallai. He was then appointed as a research assistant at Eötvös Loránd University, an appointment he held for four years from 1971 to 1975. During this time he spent the year 1972-73 at Vanderbilt University in Nashville, Tennessee in the United States. In 1975 he moved to the József Attila University in Szeged where he was appointed as a Docent but, three years later, he was promoted to professor filling the Chair of Geometry. In 1977 the Hungarian Academy of Sciences awarded him the degree Dr.Math.Sci. He spent the academic year 1978-79 at the University of Waterloo in Canada then in 1979, at the age of thirty-one, he became a member of the Hungarian Academy of Sciences making him by far the youngest member ever of the Hungarian Academy of Sciences. He left Szeged in 1983 when appointed to the Chair of Computer Science at Eötvös Loránd University in Budapest.

In 1993 Lovász gave up the Chair of Computer Science at Eötvös Loránd University but retained a professorship there. He left the Chair in Budapest to take up the William K Lanman professorship of Computer Science and Mathematics at Yale University in the United States. In 1999 he left academia to take up the position of Senior Researcher at Microsoft Research but he returned to Hungary in 2006 to become Director of the Mathematical Institute of Eötvös Loránd University.

His research involves deep results on combinatorial optimization, algorithms, complexity, graph theory, and random walks, areas which span mathematics and theoretical computer science. He is perhaps best known for the widely used 'LLL algorithm' named after Arjen K Lenstra, Hendrik W Lenstra and László Lovász who first gave the algorithm in their joint paper Factoring Polynomials with Rational Coefficients (1982). The algorithm gives an efficient basis reduction method for point lattices. We give an indication of Lovász's contributions by quoting from the citation for the Wolf Prize which he received in 1999 [2]:-

László Lovász has obtained ground-breaking results in discrete mathematics that have had 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. Lovász also contributed to the PCP characterization of NP and 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.

Before looking at further honours and prizes awarded to Lovász we give details of the outstanding books, both research monographs and teaching texts, he has written. In 1979 he published Combinatorial problems and exercises (1979). We quote from the Preface of this classic text:-

Having vegetated on the fringes of mathematical science for centuries, combinatorics has now burgeoned into one of the fastest growing branches of mathematics - undoubtedly so if we consider the number of publications in this field, its applications in other branches of mathematics and in other sciences, and also the interest of scientists, economists and engineers in combinatorial structures. The mathematical world was attracted by the successes of algebra and analysis and only in recent years has it become clear, due largely to problems arising from economics, statistics, electrical engineering and other applied sciences, that combinatorics, the study of finite sets and finite structures, has its own problems and principles. These are independent of those in algebra and analysis but match them in difficulty, practical and theoretical interest and beauty. Yet the opinion of many first-class mathematicians about combinatorics is still in the pejorative. While accepting its interest and difficulty, they deny its depth. It is often forcefully stated that combinatorics is a collection of problems which may be interesting in themselves but are not linked and do not constitute a theory. It is easy to obtain new results in combinatorics or graph theory because there are few techniques to learn, and this results in a fast-growing number of publications. The above accusations are clearly characteristic of any field of science at an early stage of its development - at the stage of collecting data. As long as the main questions have not been formulated and the abstractions to a general level have not been carried through, there is no way to distinguish between interesting and less interesting results - except on an aesthetic basis, which is, of course, too subjective. Those techniques whose absence has been disapproved of above await their discoverers. So underdevelopment is not a case against, but rather for, directing young scientists toward a given field. In my opinion, combinatorics is now growing out of this early stage. There are techniques to learn: enumeration techniques, matroid theory, the probabilistic method, linear programming, block design constructions, etc. There are branches which consist of theorems forming a hierarchy and which contain central structure theorems forming the backbone of study: connectivity of graphs (network flows) or factors of graphs, just to pick two examples from graph theory. There are notions abstracted from many nontrivial results, which unify large parts of the theory, such as matroids or the concept of good characterization. My feeling is that it is no longer possible to obtain significant results without the knowledge of these facts, concepts and techniques. (Of course, exceptions may occur, since the field is destined to cover such a large part of the world of mathematics that entirely new problems may still arise.)

Frank Harary began a review of the book as follows:-

This book is a classic. The author masterfully analyzes the proof techniques utilized in 607 different results partitioned into ... fifteen sections.

In 1993 Lovász produced a second edition, writing in the Preface:-

When the publishers of this book asked me to revise and update my problem book for a second edition, I had to decide how much to change, taking into consideration the fast development of the field (but also that the first edition was out of print). Combinatorics has grown a lot in the last decade, especially in those fields interacting with other branches of mathematics, like polyhedral combinatorics, algebraic combinatorics, combinatorial geometry, random structures and, most significantly, algorithmic combinatorics and complexity theory. (The theory of computing has so many applications in combinatorics, and vice versa, that sometimes it is difficult to draw the border between them.) But combinatorics is a discipline in its own right, and this makes this collection of exercises (subject to some updating) still valid. I decided not to change the structure and main topics of the book. Any conceptual change (like introducing algorithmic issues consistently, together with an analysis of the algorithms and the complexity classification of the algorithmic problems) would have meant writing a new book. I could not resist, however, working out a series of exercises on random walks on graphs, and their relations to eigenvalues, expansion properties, and electrical resistance (this area has classical roots but has grown explosively in the last few years).

Other books by Lovász are (with Michael D Plummer) Matching theory (1986) about which Knut Richter writes:-

This excellent book is mainly addressed to insiders of graph theory, combinatorics and discrete optimization.

Also in 1986, An algorithmic theory of numbers, graphs and convexity was published. Arjen Lenstra writes:-

This book presents a nice survey of some recent developments towards the efficient solution of computational problems in areas like graph theory, number theory, and combinatorial optimization.

Two years later Lovász published (with Martin Grötschel and Alexander Schrijver) Geometric algorithms and combinatorial optimization (1988); a second edition appeared in 1993. Jürgen Köhler reviewed the first edition:-

The authors review modern developments in mathematical optimization, discuss classical results and present many new results. ... The authors present, on a high level, a great number of results on this topic and give them their best form: this is an optimal monograph.

Next, written in collaboration with Bernhard Korte and Rainer Schrader, he published Greedoids (1991). Ulrich Faigle explains:-

There are two fundamentally different aspects of greedoids. One may think of greedoids as set systems obeying a relaxation of the matroid independence axioms in that not necessarily every subset of an independent set is independent. Viewed from this angle, structural theory of greedoids amounts to the question of how much of matroid theory is retained under this relaxed axiomatic assumption. The second aspect sees greedoids as finite languages over alphabets that are closed with respect to taking prefixes of words and have the property that any nonmaximal word may be augmented with some letter in any longer word.

In 2003 he wrote the textbook (with Josef Pelikan and Katalin L Vesztergombi) Discrete mathematics. Robin Wilson writes:-

In recent years there has been a plethora of textbooks on discrete mathematics, designed as a counter-balance to the over-emphasis on calculus in colleges and universities. This book is a welcome addition to these, being written in a delightfully informal style by three well-known practitioners in the field.

In addition to the Grünwald Géza Prize mentioned above, Lovász was awarded: the George Pólya Prize in 1979; the Best Information Theory Paper Award from the IEEE in 1981; the Ray D Fulkerson Prize awarded jointly to Lovasz, Grötschel and Schrijver for their paper The ellipsoid method and its consequences in combinatorial optimisation (1981); the State Prize, Hungary in 1985; the Tibor Szele Medal from the Bolyai Society in 1992; the Brouwer Medal from the Dutch Mathematical Society in 1993; the National Order of Merit of Hungary in 1998; the Bolzano Medal from the Czech Mathematical Society in 1998; the Wolf Prize, Israel in 1999; and the Knuth Prize in 1999. The citation for this award reads:-

Lovász had an enormous influence on the theory of algorithms. He has made fundamental discoveries that have became standard tools in theoretical computer science. The Lovász Local lemma, Lattice Basis Reduction - finding short vectors in lattices, and the application of the ellipsoid method for various convex programming problems have all become standard tools in a wide range of areas of algorithms and complexity. Lovász's contribution to the connection between hardness of approximation and probabilistic proofs was essential. In addition to his fundamental contributions in algorithms Laci Lovász has also written a number of beautiful books all emphasizing algorithms in a variety of topics.

Continuing to honours given in the present millennium, he received the Corvin Chain from the Hungarian Government in 2001 and the Gödel Prize in 2001 for the paper Interactive Proofs and the Hardness of Approximating Cliques written with Uriel Feige, Shafi Goldwasser, Shmuel Safra and Mario Szegedy. In 2006 the Institute for Operations Research and the Management Sciences awarded Lovász its John von Neumann Theory Prize. The award came with the following citation:-

László Lovász has held positions at universities in Hungary and the US as well as at Microsoft Research and is presently the director of the Mathematical Institute of the Eötvös Loránd University in Budapest. He first became well known when he proved the Perfect Graph Conjecture in 1972, at the age of 24. In 1979 he solved a long-standing problem of C Shannon in coding theory by assigning vectors to the vertices of a graph and formulating an associated semidefinite programming problem; the approach has since become a powerful tool in attacking combinatorial optimization problems. In1991, he and Schrijver showed the power of lift-and-project methods in 0-1 integer programming problems and the potential of semidefinite programming techniques to obtain tight relaxations. Lovász has also made key contributions to many topics in graph theory using novel techniques, to randomized algorithms and to submodular function minimization. Lovász will become the President of the International Mathematical Union next year. He is a member of the Hungarian, European, Russian and Dutch Academies of Sciences.

Lovász was awarded the János Bolyai Research Prize in 2007, elected to the Swedish Academy of Sciences in the same year, and awarded Hungary's Széchenyi Grand Prize on 15 March 2008. He received the Advanced Grant of the European Research Council in August 2008. In November 2008 Lovász was awarded the Bolyai Grand Prize of the János Bolyai Foundation and, on 3 July 2009, he was elected an honorary member of the London Mathematical Society.

Finally we mention that, in 1990, he was a plenary speaker at the International Congress of Mathematicians held in Kyoto. His lecture Geometric algorithms and algorithmic geometry appeared in the conference proceeding and also as a video. He was also a plenary speaker at the British Mathematical Colloquium at Exeter in 1988 when he lectured on Lattice points in convex bodies.

Articles:

1. A Jackson, Lovász receives Bolyai prize, Notices Amer. Math. Soc. 55 (2) (2008), 264.
2. Lovász and Stein Share 1999 Wolf Prize in Mathematics, Notices Amer. Math. Soc. 46 (5) (1999), 566-567.
3. L Lovász, Paul Erdos is 80, in L Babai, A Hajnal, L Lovász and V T Sós (eds.), Combinatorics, Paul Erd›s is Eighty 1 (János Bolyai Mathematical Society, Budapest, Hungary, 1993), 9.