Miklós Ajtai (born 2 July 1946) is a computer scientist at the IBM Almaden Research Center, United States.
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.
[2] 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.
The corresponding lower bound was proved by Kim only in 1995, a result that earned him a Fulkerson Prize.
For his numerous contributions in Theoretical Computer Science, he received the Knuth Prize.