Miklós Ajtai

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
Instituições IBM Almaden Research Center
Campo(s) ciência da computação, teoria da complexidade

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

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 ct2/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 m3 / 100n2 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.

Ligações externas

Ícone de esboço Este artigo sobre um(a) cientista da computação é um esboço. Você pode ajudar a Wikipédia expandindo-o.