PROFILBARU.COM

Miklos Ajtai
Miklos Ajtai
Born	2 July 1946 (age 78); Budapest, Second Republic of Hungary
Nationality	Hungarian-American
Alma mater	Hungarian Academy of Sciences
Awards	Knuth Prize (2003)
	Scientific career
Fields	Computational complexity theory
Institutions	IBM Almaden Research Center

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. He is a member of the U.S. National Academy of Sciences.^[2]

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. Ajtai and Szemerédi proved the corners theorem, an important step toward higher-dimensional generalizations of the Szemerédi theorem. 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, Newborn, and Szemerédi, Ajtai proved the crossing number inequality, that any drawing of a graph with n vertices and m edges, where m > 4n, has at least m³ / 100n² crossings. Ajtai and Dwork devised in 1997 a lattice-based public-key cryptosystem; Ajtai has done extensive work on lattice problems. For his numerous contributions in Theoretical Computer Science, he received the Knuth Prize.^[1]

Ajtai received his Candidate of Sciences degree in 1976 from the Hungarian Academy of Sciences.^[3] Since 1995, he has been an external member of the Hungarian Academy of Sciences.

In 1998, he was an Invited Speaker of the International Congress of Mathematicians in Berlin.^[4] In 2012, he was elected as a Fellow of the American Association for the Advancement of Science.^[5] In 2021, he was elected a member of the National Academy of Sciences.^[6]

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

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

^ ^a ^b "Archived copy". Archived from the original on 2021-05-14. Retrieved 2015-02-10.{{cite web}}: CS1 maint: archived copy as title (link)
^ "News from the National Academy of Sciences". 26 April 2021. Retrieved 1 July 2021. Newly elected members and their affiliations at the time of election are: ... Ajtai, Miklós; IBM Emeritus Researcher, IBM Almaden Research Center, Los Gatos, Calif.
^ Magyar Tudományos Akadémia, Almanach, 1986, Budapest.
^ Ajtai, Miklós (1998). "Worst-case complexity, average-case complexity and lattice problems". Documenta Mathematica: 421–428.
^ AAAS Members Elected as Fellows, AAAS, 29 November 2012
^ "National Academy of Sciences Elects New Members — Including a Record Number of Women — and International Members". nasonline.org. 26 April 2021. Retrieved 28 April 2021.