# László Lovász

> 1948– · Mathematician
>
> **Recorded contribution:** Graph theory; Lovász Local Lemma; lattice basis reduction (LLL algorithm); combinatorial optimization

## How to use this dossier

Read for a causal chain, not a hero story: inherited problem → contribution → mechanism → downstream capability → limit. Then close the page and complete the reconstruction exercise from memory.

## 1. Historical orientation

László Lovász (born 1948) is a Hungarian mathematician whose work connects graph theory, combinatorics, optimization, probability, and algorithms. The Lovász local lemma, first developed with Paul Erdős, proves that a collection of mostly independent bad events can all be avoided even when a simple union bound fails. The LLL lattice-basis-reduction algorithm—created with Arjen and Hendrik Lenstra—finds a reasonably short, nearly orthogonal basis in polynomial time and has major uses in number theory and cryptanalysis. Lovász's career exemplifies how structural theorems become algorithms, but each named result is collaborative and the registry's list should not merge them into sole authorship.

## 2. The problem inherited

Combinatorial objects often seem to exist by probability arguments without an efficient construction, while arbitrary lattice bases hide short useful vectors.

## 3. The central contribution

Lovász developed structural and algorithmic tools that exploit limited dependency or geometric reduction to make hard combinatorial spaces tractable.

## 4. Reconstruct the mechanism

1. For lattice reduction, orthogonalize basis vectors conceptually with Gram–Schmidt and measure projection coefficients.
2. Size-reduce a basis vector by subtracting integer multiples of earlier vectors when coefficients are too large.
3. Test the Lovász condition relating consecutive orthogonalized lengths; swap vectors when it fails.
4. Repeat reduction and swaps until the condition holds, yielding a polynomial-time reduced basis with bounded quality.

## 5. What changed downstream

- LLL enabled polynomial-time factoring of rational polynomials and many computational-number-theory methods.
- Lattice reduction became important in cryptanalysis and modern lattice cryptography.
- The local lemma influenced randomized algorithms, graph coloring, scheduling, and constructive probability.

## 6. Attribution, limits, and uncertainty

- The Lenstra brothers are LLL coauthors; Erdős is local-lemma coauthor and later constructive variants have other authors.
- LLL gives an approximation guarantee, not necessarily the shortest lattice vector.
- Lattice dimension, numeric precision, and basis quality strongly affect practical performance.

## 7. Reconstruction lab

Apply two-dimensional size reduction and the Lovász swap condition to a poor integer basis, plotting the fundamental parallelogram before and after. Compare the reduced first vector with the true shortest vector.

## 8. Evidence trail

- [Factoring Polynomials with Rational Coefficients](https://doi.org/10.1007/BF01457454) — Mathematische Annalen
- [László Lovász](https://abelprize.no/abel-prize-laureates/2021) — Abel Prize

---

*Research checked 2026-08-09. Dates, roles, and claims about living people are historical snapshots. Linked sources remain the authority; this dossier is original instructional synthesis.*