Miklós Ajtai

From Wikipedia, the free encyclopedia
  (Redirected from Miklos Ajtai)
Jump to navigation Jump to search
Miklos Ajtai
Born (1946-07-02) 2 July 1946 (age 75)
Alma materHungarian Academy of Sciences
AwardsKnuth Prize (2003)[1]
Scientific career
FieldsComputational complexity theory
InstitutionsIBM 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[edit]

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 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]


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, Miklos: Optimal lower bounds of the Korkine-Zolotareff parameters of a lattice and for Schnorr´s algorithm for the shortest vector problem, in: Theory of Computering, Vol. 4, ppp 21-51.[7]
  • Ajtai, Miklos: A Non-linear Time Lower Bound for Boolean Branching Programs, in: Theory of Computering, Vol. 1, pp 149-176.[7]
  • Ajtai, Miklos: Generating Hard Instances of Lattice Problems. Electronic Colloquium on Computational Completity, p 1-29.[8]

Selected papers[edit]

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


  1. ^ a b http://www.sigact.org/Prizes/Knuth/2003.html
  2. ^ "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.
  3. ^ Magyar Tudományos Akadémia, Almanach, 1986, Budapest.
  4. ^ Ajtai, Miklós (1998). "Worst-case complexity, average-case complexity and lattice problems". Doc. Math. (Bielefeld) Extra Vol. ICM Berlin, 1998, vol. III. pp. 421–428.
  5. ^ AAAS Members Elected as Fellows, AAAS, 29 November 2012
  6. ^ "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.
  7. ^ a b "Articles by Miklós Ajtai". Theory of Computing. Retrieved 23 October 2019.
  8. ^ "Generating Hard Instances of Lattice Problems" (PDF). semanticscholar.org. S2CID 1480070. Archived from the original (PDF) on 9 March 2019. Retrieved 23 October 2019. Cite journal requires |journal= (help)

External links[edit]