Miklós Ajtai (nacido el 2 de julio de 1946) es un informático del IBM Almaden Research Center , Estados Unidos. En 2003, recibió el Premio Knuth por sus numerosas contribuciones en el 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". Es miembro de la Academia Nacional de Ciencias de Estados Unidos . [2]
Uno de los resultados de Ajtai establece que la longitud de las pruebas en 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 "dos estructuras contables cualesquiera que sean equivalentes de segundo orden también son isomorfas " es consistente 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 ct 2 /log t para el número de Ramsey R (3, t ). Kim no demostró el límite inferior correspondiente hasta 1995, resultado que le valió el Premio Fulkerson . Con Chvátal , Newborn y Szemerédi , Ajtai demostró la desigualdad del número de cruces , que cualquier dibujo de un gráfico con n vértices y m aristas, 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 extenso trabajo sobre problemas de redes . Por sus numerosas contribuciones en informática teórica, recibió el premio Knuth. [1]
Ajtai recibió su título de Candidato en Ciencias en 1976 de la Academia de Ciencias de Hungría . [3] Desde 1995 es miembro externo de la Academia de Ciencias de Hungría .
En 1998, fue orador invitado del Congreso Internacional de Matemáticos en Berlín. [4] En 2012, fue elegido miembro de la Asociación Estadounidense para el Avance de la Ciencia . [5] En 2021, fue elegido miembro de la Academia Nacional de Ciencias. [6]
{{cite web}}: Mantenimiento CS1: copia archivada como título ( enlace )Los miembros recién elegidos y sus afiliaciones en el momento de la elección son: ... Ajtai, Miklós; Investigador emérito de IBM, IBM Almaden Research Center, Los Gatos, California.