Miklós Ajtai

Miklós Ajtai
Born	(1946-07-02) July 2, 1946
Occupation	Computer scientist
Employer	IBM Almaden Research Center
Known for	Sorting network algorithm, lattice-based public-key cryptosystem, theoretical computer science contributions
Awards	Knuth Prize (2003)
Honors	Member of the U.S. National Academy of Sciences, Fellow of the American Association for the Advancement of Science, external member of the Hungarian Academy of Sciences

Miklós Ajtai (born July 2, 1946) is a distinguished computer scientist affiliated with the IBM Almaden Research Center in the United States. He was honored with the Knuth Prize in 2003, recognizing his influential work, which includes the development of a renowned sorting network algorithm in collaboration with J. Komlós and Endre Szemerédi, as well as groundbreaking results such as exponential lower bounds, superlinear time-space tradeoffs for branching programs, among other significant contributions. Ajtai is also a member of the U.S. National Academy of Sciences.

Selected results

Ajtai established that proofs within propositional logic concerning the pigeonhole principle for n elements increase in size faster than any polynomial function of n. He demonstrated that the proposition "any two countable structures that are equivalent under second-order logic are necessarily isomorphic" is both consistent with and independent from ZFC. Together with Endre Szemerédi, he proved the corners theorem, which extends higher-dimensional variants of the Szemerédi theorem. In partnership with Komlós and Szemerédi, he derived the upper bound of ct²/log t for the Ramsey number R(3,t). In 1984, collaborating with Komlós and Tusnády, he established the AKT optimal matching theorem, whose lower bound was subsequently confirmed by Kim in 1995, a result that received the prestigious Fulkerson Prize. Working alongside Chvátal, Newborn, and Szemerédi, Ajtai proved the crossing number inequality: any graph drawn with n vertices and m edges (with ) must have at least crossings. In 1997, Ajtai and Dwork introduced a lattice-based public-key cryptosystem. His extensive investigations into lattice problems have significantly influenced theoretical computer science, a fact underscored by his Knuth Prize recognition.

Biography

Ajtai obtained his Candidate of Sciences degree from the Hungarian Academy of Sciences in 1976. He has been an external member of this Academy since 1995. In 1998, he was invited to speak at the International Congress of Mathematicians held in Berlin. He was named a Fellow of the American Association for the Advancement of Science in 2012 and was inducted into the National Academy of Sciences in 2021.

Bibliography

• Ajtai, Miklós. "Optimal lower bounds for the Korkine-Zolotareff parameters of a lattice and for Schnorr's algorithm for the shortest vector problem." Theory of Computing, May 10, 2008, 4:21–51.
• Ajtai, Miklós. "A Non-linear Time Lower Bound for Boolean Branching Programs." Theory of Computing, October 5, 2005, 1:149–176.
• Ajtai, M. "Generating hard instances of lattice problems (Extended abstract)." Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96, 1996, pp. 99–108.

Selected papers

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

External links

• Official homepage of Miklós Ajtai