Miklós Ajtai (nacido el 2 de julio de 1946) es un científico informático del IBM Almaden Research Center , Estados Unidos. En 2003, recibió el Premio Knuth por sus numerosas contribuciones al campo, incluido un algoritmo de red de clasificación clásico (desarrollado conjuntamente con J. Komlós y Endre Szemerédi ), límites inferiores exponenciales, compensaciones espacio-temporales superlineales para programas de ramificación y otros " resultados únicos y espectaculares ".
Miklos Ajtai | |
---|---|
Nació | |
Nacionalidad | Húngaro-estadounidense |
alma mater | Academia de Ciencias de Hungría |
Premios | Premio Knuth (2003) [1] |
Carrera científica | |
Campos | Teoría de la complejidad computacional |
Instituciones | Centro de investigación de IBM Almaden |
Resultados seleccionados
Uno de los resultados de Ajtai establece que la longitud de las pruebas en la lógica proposicional del principio de casillero para n elementos crece más rápido que cualquier polinomio en n . También demostró que la afirmación "cualesquiera dos estructuras contables que sean equivalentes de segundo orden también son isomorfas " es a la vez coherente e independiente de ZFC . Ajtai y Szemerédi demostraron el teorema de las esquinas , un paso importante hacia generalizaciones de dimensiones superiores del teorema de Szemerédi . Con Komlós y Szemerédi demostró el límite superior de ct 2 / log t para el número de Ramsey R (3, t ). El límite inferior correspondiente fue probado por Kim solo en 1995, un resultado que le valió un Premio Fulkerson . Con Chvátal , recién nacido , y Szemerédi , Ajtai probó el número desigualdad de cruce , que cualquier dibujo de un gráfico con n vértices y m bordes, donde m > 4 n , tiene al menos m 3 /100 n 2 cruces . Ajtai y Dwork idearon en 1997 un criptosistema de clave pública basado en celosía ; Ajtai ha realizado un trabajo extenso sobre problemas de celosía . Por sus numerosas contribuciones en Informática Teórica recibió el Premio Knuth. [1]
Biodatos
Ajtai recibió su título de Candidato en Ciencias en 1976 de la Academia de Ciencias de Hungría . [2] Desde 1995 ha sido miembro externo de la Academia de Ciencias de Hungría .
En 1998 fue Orador Invitado del Congreso Internacional de Matemáticos en Berlín. [3] En 2012 fue elegido miembro de la Asociación Estadounidense para el Avance de la Ciencia . [4] En 2021 fue elegido miembro de la Academia Nacional de Ciencias. [5]
Bibliografía
- Ajtai, Miklos: Límites inferiores óptimos de los parámetros de Korkine-Zolotareff de una red y del algoritmo de Schnorr para el problema del vector más corto, en: Teoría de la Computación, Vol. 4, págs. 21-51. [6]
- Ajtai, Miklos: Un límite inferior de tiempo no lineal para programas de ramificación booleana, en: Teoría de la Computación, Vol. 1, págs. 149-176. [6]
- Ajtai, Miklos: Generación de instancias difíciles de problemas de celosía. Coloquio electrónico sobre completitud computacional, p. 1-29. [7]
Artículos seleccionados
- Ajtai, M. (1979), "Isomorfismo y equivalencia de orden superior", 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), "Mayor componente aleatorio de un k -cube", Combinatorica , 2 (1): 1–7, doi : 10.1007 / BF02579276.
Referencias
- ^ a b http://www.sigact.org/Prizes/Knuth/2003.html
- ^ Magyar Tudományos Akadémia, Almanach, 1986, Budapest.
- ^ Ajtai, Miklós (1998). "Complejidad del peor de los casos, complejidad del caso medio y problemas de celosía" . Doc. Matemáticas. (Bielefeld) Extra Vol. ICM Berlín, 1998, vol. III . págs. 421–428.
- ^ Miembros de AAAS elegidos como becarios , AAAS, 29 de noviembre de 2012
- ^ "La Academia Nacional de Ciencias elige nuevos miembros, incluido un número récord de mujeres, y miembros internacionales" . nasonline.org . 26 de abril de 2021 . Consultado el 28 de abril de 2021 .
- ^ a b "Artículos de Miklós Ajtai" . Teoría de la Computación . Consultado el 23 de octubre de 2019 .
- ^ "Generación de instancias duras de problemas de celosía" (PDF) . semanticscholar.org. Archivado desde el original (PDF) el 9 de marzo de 2019 . Consultado el 23 de octubre de 2019 .
enlaces externos
- Página de inicio de Miklós Ajtai
- Lista de publicaciones de Microsoft Academic
- Miklós Ajtai en el Proyecto de genealogía matemática