This article relies largely or entirely upon a single source. Please help improve this article by introducing appropriate citations of additional sources. (December 2009)

The native form of this personal name is Ajtai Miklós. This article uses the Western name order.

Miklós Ajtai (born 2 July 1946, Budapest, Hungary) is a computer scientist at the IBM Almaden Research Center. In 2003 he received the Knuth Prize for his numerous contributions to the field, including a classic sorting network algorithm (developed jointly with J. Komlós and Endre Szemerédi), exponential lower bounds, superlinear time-space tradeoffs for branching programs, and other "unique and spectacular" results.

Contents 1 Selected results 2 Biodata 3 Selected papers 4 See also 5 References 6 External links

[edit] Selected results

One of Ajtai's results states that the length of proofs in propositional logic of the pigeonhole principle for n items grows faster than any polynomial in n. He also proved that the statement "any two countable structures that are second-order equivalent are also isomorphic" is both consistent with and independent of ZFC. With Komlós and Szemerédi he proved the ct²/log t upper bound for the Ramsey number R(3,t). The corresponding lower bound was proved by Kim only in 1995, a result that earned him a Fulkerson Prize. With Chvátal, M. M. Newborn and Szemerédi Ajtai proved that a planar graph with n vertices and m edges, where m > 4n has at least m³ / 100n² crossings.

[edit] Biodata

Ajtai received his Ph.D. in 1976 from Eötvös Loránd University.^[1] Since 1995 he has been an external member of the Hungarian Academy of Sciences.

[edit] Selected papers

1. Ajtai, M. (1979), "Isomorphism and higher order equivalence", Annals of Mathematical Logic 16 (3): 181–203, doi:10.1016/0003-4843(79)90001-9 .
2. Ajtai, M.; Komlós, J.; Szemerédi, E. (1982), "Largest random component of a k-cube", Combinatorica 2 (1): 1–7, doi:10.1007/BF02579276 .

[edit] See also

• Ajtai-Dwork cryptosystem

[edit] References

1. ^ Miklós Ajtai at the Mathematics Genealogy Project

[edit] External links

• Ajtai's home page

v • d • e Knuth Prize laureates Yao (1996) · Valiant (1997) · Lovász (1999) · Ullman (2000) · Papadimitriou (2002) · Ajtai (2003) · Yannakakis (2005) · Lynch (2007) · Strassen (2008)

Persondata
NAME	Ajtai, Miklós
ALTERNATIVE NAMES
SHORT DESCRIPTION	Computer scientist
DATE OF BIRTH	2 July 1946
PLACE OF BIRTH	Budapest, Hungary
DATE OF DEATH
PLACE OF DEATH

This article about a Hungarian scientist is a stub. You can help Wikipedia by expanding it. v • d • e

This biographical article relating to a computer scientist is a stub. You can help Wikipedia by expanding it. v • d • e