利用者:Trunk5772/Miklós Ajtai
| Miklos Ajtai | |
|---|---|
| 生誕 |
1946年7月2日（78歳） Budapest, Second Republic of Hungary |
| 居住 | San Jose, California, United States |
| 国籍 | Hungarian-American |
| 研究分野 | Computational complexity theory |
| 研究機関 | IBM Almaden Research Center |
| 出身校 | Hungarian Academy of Sciences |
| 主な受賞歴 | Knuth Prize (2003)[1] |
| プロジェクト:人物伝 | |
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.
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.
Biodata
[編集]Ajtai received his Candidate of Sciences degree in 1976 from the Hungarian Academy of Sciences.[2] Since 1995 he has been an external member of the Hungarian Academy of Sciences.
Selected papers
[編集]- 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.
References
[編集]- ^ http://www.sigact.org/Prizes/Knuth/2003.html
- ^ Magyar Tudományos Akadémia, Almanach, 1986, Budapest.
External links
[編集]- Miklós Ajtai home page
- 著作一覧 - Microsoft Academic Search.
- Trunk5772/Miklós Ajtai - Mathematics Genealogy Project
[[Category:1946年生]] [[Category:アメリカ合衆国の計算機科学者]] [[Category:ハンガリーの数学者]] [[Category:IBMの人物]] [[Category:存命人物]] [[Category:理論計算機科学者]]