Miklós Ajtai

Miklós Ajtai (Budapeste, 2 de julho de 1946) é um cientista da computação húngaro.

Miklós Ajtai
Nascimento	2 de julho de 1946 (78 anos) Budapeste
Residência	San José
Nacionalidade	húngaro
Cidadania	Hungria
Progenitores	Miklós Ajtai
Alma mater	Academia de Ciências da Hungria
Ocupação	matemático, cientista de computação, engenheiro
Distinções	Prêmio Knuth (2003)
Empregador(a)	IBM, Universidade McGill, Universidade da Califórnia em San Diego, Instituto de Tecnologia de Massachusetts
Orientador(a)(es/s)	András Hajnal
Instituições	IBM Almaden Research Center
Campo(s)	ciência da computação, teoria da complexidade
[edite no Wikidata]

Trabalha no IBM Almaden Research Center, Estados Unidos.

Em 2003 recebeu o Prêmio Knuth, por seus diversos trabalhos em ciência da computação, incluindo um algoritmo clássico de classificação de rede (desenvolvido juntamente com János Komlós e Endre Szemerédi), ínfimo exponencial, implicações tempo-espaço superlineares para ramificação de programas, o outros resultados.

Vida

Ajtai graduou-se em 1976 na Academia de Ciências da Hungria,^[1] da qual é desde 1995 um membro externo.

Resultados selecionados

Um dos resultados de Ajtai estabelece que o comprimento das provas em lógica proposicional do princípio da casa dos pombos para n itens cresce mais rápido que qualquer polinômio em n. Também provou a afirmação que "quaisquer duas estruturas de interpretação contáveis que são equivalentes de segunda ordem são também isomórficas" é consistente com e independente dos axiomas de Zermelo-Fraenkel. Ajtai e Endre Szemerédi provaram o teorema dos vértices (corners theorem), um passo fundamental para generalizações dimensionais superiores do teorema de Szemerédi. Juntamente com János Komlós e Endre Szemerédi provou o limite superior ct²/log t do número de Ramsey R(3,t). O correspondente limite inferior foi provado por Jeong Han Kim somente em 1995, o que lhe valeu um Prêmio Fulkerson. Com Václav Chvátal, M. M. Newborn e Endre Szemerédi, Ajtai provou que um grafo planar com n vértices e m arestas, sendo m > 4n, tem no mínimo m³ / 100n² crossings.

Publicações selecionadas

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.

Referências

1. Magyar Tudományos Akadémia, Almanach, 1986, Budapest.