Miklós Ajtai
# Miklós Ajtai

Miklós Ajtai (2 juillet 1946, Budapest, Hongrie - ) est un mathématicien hongrois et chercheur en informatique au centre de recherches IBM d'Almaden. En 2003, il reçoit le prix Knuth pour ses nombreuses contributions au domaine, notamment un algorithme de tri par réseau, développé avec János Komlós et Endre Szemerédi.

## Biographie

Miklós Ajtai a reçu son PhD en 1976, à l'université Loránd Eötvös, sous la direction de Andras Hajnal.

## Travaux

Miklós Ajtai a surtout travaillé selon une approche combinatoire, notamment par théorie de Ramsey. En théorie de la complexité, il a prouvé, par la logique, que la fonction parité ne pouvait pas être calculée dans $AC^0.$

Il a aussi copublié avec Paul Erdős (donc son nombre d'Erdős est 1).

### Quelques publications

* (en) « Isomorphism and higher order equivalence », Annals of Mathematical Logic, vol. 16, $n^o$ 3, 1979, p. 181-203 DOI 10.1016/0003-4843(79)90001-9
* (en) (avec J. Komlós et E. Szemerédi) « Largest random component of a k-cube », Combinatorica, vol. 2, $n^o$ 1, 1982, p. 1-7 DOI 10.1007/BF02579276

## Prix

Miklós Ajtai a gagné le prix Donald E. Knuth en 2003.

