Miklós Ajtai

Miklós Ajtai ( born July 2, 1946 in Budapest) is a Hungarian computer scientist.

Ajtai received his doctorate in 1976 at the Eotvos Lorand University in Andras Hajnal and then himself taught at the university. He is a scientist at IBM's Almaden Research Center in San Jose.

Ajtai is particularly concerned with complexity theory, combinatorics and mathematical logic. He also dealt with cryptography, starting from its investigation of lattice problems and the difficulty of calculation. Further research topics are sorting, finite model theory, expander graphs, deterministic simulation of probabilistic algorithms. Particularly important in the complexity theory and cryptography back in 1996 its construction of numerical grids, where it is just as hard in the average case, with respect to approximate their shortest vector of its length (up to a polynomial factor in the dimension of the lattice ), as in the most difficult case.

Ajtai is a foreign member of the Hungarian Academy of Sciences since 1995. In 2003 he received the Knuth Prize.