Miklós Ajtai (* 2. Juli 1946 in Budapest) ist ein ungarischer Informatiker.

Ajtai wurde 1976 an der Loránd-Eötvös-Universität bei András Hajnal promoviert und lehrte dann selbst an der Universität. Er ist Wissenschaftler am IBM Almaden Research Center in San Jose.

Ajtai beschäftigt sich insbesondere mit Komplexitätstheorie, Kombinatorik und Mathematischer Logik. Außerdem beschäftigte er sich mit Kryptographie ausgehend von seiner Untersuchung von Gitterproblemen und deren Berechnungsschwierigkeit. Weitere Forschungsfelder sind Sortierung, endliche Modelltheorie, Expander Graphen, deterministische Simulation probabilistischer Algorithmen. Besondere Bedeutung für die Komplexitätstheorie und die Kryptographie erlangte 1996 seine Konstruktion von Zahlengittern, bei denen es im durchschnittlichen Fall genau so schwer ist, ihren kürzesten Vektor bezüglich seiner Länge zu approximieren (bis auf einen polynomialen Faktor in der Dimension des Gitters), wie im schwierigsten Fall.^[1]

Ajtai ist seit 1995 auswärtiges Mitglied der Ungarischen Akademie der Wissenschaften, seit 2021 der National Academy of Sciences. 2003 erhielt er den Knuth-Preis. Für 2025 wurde ihm die John-von-Neumann-Medaille zugesprochen.

• Satz von Ajtai-Komlós-Tusnády

1. ↑ Generating hard instances of lattice problems (extended abstract). Proceedings of the twenty-eighth annual ACM symposium on Theory of computing (STOC '96), AMS 1996, S. 99–108

• Homepage