Miklós Ajtai
Lua error in package.lua at line 80: module 'strict' not found.
<templatestyles src="Module:Hatnote/styles.css"></templatestyles>
Miklos Ajtai | |
---|---|
Born | Budapest, Second Republic of Hungary |
2 July 1946
Residence | San Jose, California, United States of America |
Nationality | Hungarian-American |
Fields | Computational complexity theory |
Institutions | IBM Almaden Research Center |
Alma mater | Hungarian Academy of Sciences |
Notable awards | Knuth Prize (2003)[1] |
Miklós Ajtai (born 2 July 1946) is a computer scientist at the IBM Almaden Research Center, USA. 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 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.[2] Since 1995 he has been an external member of the Hungarian Academy of Sciences.
Selected papers
- Lua error in package.lua at line 80: module 'strict' not found..
- Lua error in package.lua at line 80: module 'strict' not found..
References
- ↑ 1.0 1.1 http://www.sigact.org/Prizes/Knuth/2003.html
- ↑ Magyar Tudományos Akadémia, Almanach, 1986, Budapest.
External links
- Miklós Ajtai home page
- List of publications from Microsoft Academic Search
- Miklós Ajtai at the Mathematics Genealogy Project
Lua error in package.lua at line 80: module 'strict' not found.
<templatestyles src="Asbox/styles.css"></templatestyles>
<templatestyles src="Asbox/styles.css"></templatestyles>
- 1946 births
- Living people
- Knuth Prize laureates
- Hungarian mathematicians
- Hungarian computer scientists
- Members of the Hungarian Academy of Sciences
- Theoretical computer scientists
- Hungarian expatriates in the United States
- American computer scientists
- IBM employees
- Hungarian scientist stubs
- Computer scientist stubs