1999 Knuth Prize
1999 Knuth Prize
László Lovász
The winner of the 3rd
Knuth Prize is
László Lovász.
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.
The prize committee for the 3rd Knuth Prize, consisting of Allan Borodin,
Ashok Chandra, Herbert Edelsbrunner, Christos Papadimitriou, Éva Tardos
(chair), and Avi Wigderson decided to award to prize to
Laci Lovász for this
impact on the theory of algorithms.
Created by
Ian Parberry,
May 10, 1999.
Last updated
Wed Nov 8 17:02:57 CST 2000