Miklós Ajtai
Miklos Ajtai | |
|---|---|
| Born | 2 July 1946 Almaden Research Center |
Miklós Ajtai (born 2 July 1946) is a
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
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
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]
Bibliography
- 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. .
- Ajtai, Miklós (5 October 2005). "A Non-linear Time Lower Bound for Boolean Branching Programs". Theory of Computing. 1: 149–176. .
- 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. S2CID 6864824.
Selected papers
- Ajtai, M. (September 1979). "Isomorphism and higher order equivalence". Annals of Mathematical Logic. 16 (3): 181–203. .
- Ajtai, M.; Komlós, J.; Szemerédi, E. (March 1982). "Largest random component of a k-cube". Combinatorica. 2 (1): 1–7. S2CID 7903662.
References
- ^ 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
- Miklós Ajtai home page
- Miklós Ajtai publications indexed by Microsoft Academic
- Miklós Ajtai at the Mathematics Genealogy Project
| International | |
|---|---|
| National | |
| Academics | |
| People | |
   | This article about a Hungarian scientist is a stub. You can help Wikipedia by expanding it. |