|Residence||San Jose, California, United States|
|Alma mater||Hungarian Academy of Sciences|
|Awards||Knuth Prize (2003)|
|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.
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.
In 1998 he was an Invited Speaker of the International Congress of Mathematicians in Berlin. In 2012 he was elected as a Fellow of the American Association for the Advancement of Science.
- 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.
- Ajtai, Miklos: A Non-linear Time Lower Bound for Boolean Branching Programs, in: Theory of Computering, Vol. 1, pp 149-176.
- Ajtai, Miklos: Generating Hard Instances of Lattice Problems. Electronic Colloquium on Computational Completity, p 1-29.
- Ajtai, M. (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. (1982), "Largest random component of a k-cube", Combinatorica, 2 (1): 1–7, doi:10.1007/BF02579276.
- Magyar Tudományos Akadémia, Almanach, 1986, Budapest.
- 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.
- AAAS Members Elected as Fellows, AAAS, 29 November 2012
- "Articles by Miklós Ajtai". Theory of Computing. Retrieved 23 October 2019.
- "Generating Hard Instances of Lattrice Problems" (PDF). semanticscholar.org. Retrieved 23 October 2019.
- Miklós Ajtai home page
- List of publications from 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.|
|P ≟ NP||This biographical article relating to a computer scientist is a stub. You can help Wikipedia by expanding it.|