Miklós Ajtai
Miklós Ajtai (born July 2, 1946 in Budapest ) is a Hungarian computer scientist.
Ajtai received his doctorate in 1976 from the Loránd Eötvös University under András Hajnal and then taught at the university himself. He is a scientist at the IBM Almaden Research Center in San Jose .
Ajtai is particularly concerned with complexity theory , combinatorics and mathematical logic. He also dealt with cryptography based on his investigation of lattice problems and their computational difficulty. Further research fields are sorting, finite model theory, expander graphs, deterministic simulation of probabilistic algorithms. In 1996, his construction of number grids became particularly important for complexity theory and cryptography, in which, on average, it is just as difficult to approximate their shortest vector in terms of its length (except for a polynomial factor in the dimension of the grid) as in the most difficult Case.
Ajtai has been an external member of the Hungarian Academy of Sciences since 1995. In 2003 he received the Knuth Prize .
Individual evidence
- ↑ Generating hard instances of lattice problems (extended abstract). Proceedings of the twenty-eighth annual ACM symposium on Theory of computing (STOC '96), AMS 1996, pp. 99-108
Web links
| personal data | |
|---|---|
| SURNAME | Ajtai, Miklós |
| BRIEF DESCRIPTION | Hungarian computer scientist |
| DATE OF BIRTH | July 2, 1946 |
| PLACE OF BIRTH | Budapest |