Miklós Ajtai

From Wikipedia, the free encyclopedia

Miklós Ajtai (born July 2, 1946 in 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.

[edit] Some of his works

One of his results states that the pigeonhole principle does not have a proof of polynomial length. He also proved that the statement «any two countable structures elementary equivalent in second order are isomorphic» is both consistent and independent in 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, this result earned him a Fulkerson Prize. With Chvátal, M. M. Newborn and Szemerédi he proved that if m>4n and a graph with n vertices and m edges is drawn in the plane, then there are at least m³/100n² crossings.

[edit] Awards

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

[edit] Selected papers

M. Ajtai: Isomorphism and higher order equivalence, Ann. Math. Logic, 16(1979), 181--203.
M. Ajtai, J. Komlós, E. Szemerédi: Largest random component of a k-cube, Combinatorica, 2(1982), 1--7.