Jump to content

Miklós Ajtai

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by InternetArchiveBot (talk | contribs) at 02:45, 14 July 2022 (Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.8.8) (Ost316 - 10368). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

The native form of this personal name is Ajtai Miklós. This article uses Western name order when mentioning individuals.
Miklos Ajtai
Born (1946-07-02) 2 July 1946 (age 78)
Budapest, Second Republic of Hungary
NationalityHungarian-American
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

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]

Biodata

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

  1. 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.
  2. 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

  1. ^ 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)
  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". Documenta Mathematica: 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.


Flag of HungaryScientist icon Stub icon

This article about a Hungarian scientist is a stub. You can help Wikipedia by expanding it.

P ≟ NP 

This biographical article relating to a computer scientist is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Miklós_Ajtai&oldid=1098075627"