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]
Miklos Ajtai | |
|---|---|
| Born | 2 July 1946 |
| Nationality | Hungarian-American |
| Alma mater | Hungarian Academy of Sciences |
| Awards | Knuth Prize (2003)[1] |
| Scientific career | |
| Fields | Computational complexity theory |
| Institutions | IBM Almaden Research Center |
Selected results
editOne 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 ct2/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 m3 / 100n2 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]
Biography
editAjtai 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]
Bibliography
edit- 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.
Selected papers
edit- 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.
References
edit- ^ 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.
External links
edit- Miklós Ajtai home page
- Miklós Ajtai publications indexed by Microsoft Academic
- Miklós Ajtai at the Mathematics Genealogy Project
   | This article about a Hungarian scientist is a stub. You can help Wikipedia by expanding it. |