Nati Linial

Nathan (Nati) Linial ( en hebreo : נתן (נתי) ליניאל ; nacido en 1953 en Haifa , Israel) ^{[ 1 ]} es un matemático e informático israelí , profesor en la Escuela de Ciencias de la Computación e Ingeniería Rachel y Selim Benin de la Universidad Hebrea de Jerusalén , ^{[ 2 ]} e investigador altamente citado por ISI . ^{[ 3 ]}

Linial realizó sus estudios de pregrado en el Technion y obtuvo su doctorado en 1978 en la Universidad Hebrea bajo la supervisión de Micha Perles. ^{[ 1 ] [ 4 ]} Fue investigador de posgrado en la Universidad de California, Los Ángeles, antes de regresar a la Universidad Hebrea como miembro del profesorado. ^{[ 1 ]}

En 2012 se convirtió en miembro de la Sociedad Matemática Estadounidense . ^{[ 5 ]} En 2019 ganó el Premio FOCS Test of Time por el artículo " Circuitos de profundidad constante, transformada de Fourier y capacidad de aprendizaje ", en coautoría con Yishay Mansour y Noam Nisan . ^{[ 6 ]}

• Linial, Nati (1992), "Localidad en algoritmos de gráficos distribuidos", SIAM J. Comput. , 21 (1): 193– 201, CiteSeerX 10.1.1.471.6378 , doi : 10.1137/0221015 El artículo ganó el Premio Dijkstra 2013. En palabras del comité del premio: «Este artículo ha tenido un gran impacto en los algoritmos de paso de mensajes distribuidos. Puso de relieve la noción de localidad en la computación distribuida y planteó preguntas interesantes sobre el nivel de localidad de varios problemas distribuidos, en términos de su complejidad temporal en diferentes clases de redes. Con ese objetivo, en este artículo, Linial desarrolló un modelo particularmente adecuado para estudiar la localidad, que ignora el tamaño de los mensajes, la asincronía y los fallos. Este modelo limpio permitió a los investigadores aislar los efectos de la localidad y estudiar el papel de las distancias y los vecindarios, como nociones de la teoría de grafos, y sus interrelaciones con problemas algorítmicos y de teoría de la complejidad en la computación distribuida». ^{[ 7 ]}
• Borodin, Allan ; Linial, Nathan; Saks, Michael E. (1992), "Un algoritmo óptimo en línea para sistemas de tareas métricas", J. ACM , 39 (4): 745–763 , doi : 10.1145/146585.146588 , S2CID 18783826 Este artículo sobre análisis competitivo de algoritmos en línea estudia los sistemas de tareas métricas , un modelo muy general de tareas donde se deben tomar decisiones sobre cómo atender una secuencia de solicitudes sin conocer las solicitudes futuras. Introduce el modelo de sistema de tareas métricas, describe cómo usarlo para modelar diversos problemas de planificación y desarrolla un algoritmo que, en muchas situaciones, demuestra un rendimiento óptimo.
• Linial, Nathan; Mansour, Yishay; Nisan, Noam (1993), "Circuitos de profundidad constante, transformada de Fourier y capacidad de aprendizaje", J. ACM , 40 (3): 607–620 , doi : 10.1145/174130.174138 , S2CID 16978276 Mediante el análisis armónico de funciones de la clase de complejidad AC ⁰ (una clase que representa problemas computacionales altamente paralelizable ), Linial y sus coautores demuestran que estas funciones se comportan mal como generadores de números pseudoaleatorios , pueden aproximarse bien mediante polinomios y pueden ser aprendidas eficientemente por sistemas de aprendizaje automático .
• Linial, Nathan; London, Eran; Rabinovich, Yuri (1995), "La geometría de los grafos y algunas de sus aplicaciones algorítmicas", Combinatorica , 15 (2): 215–245 , doi : 10.1007/BF01200757 , S2CID 5071936 El artículo más citado de Linial según Google Scholar , explora las conexiones entre problemas de teoría de grafos, como el problema del flujo de múltiples mercancías , y las incrustaciones de baja distorsión de espacios métricos en espacios de baja dimensión, como las dadas por el lema de Johnson-Lindenstrauss .
• Hoory, Shlomo; Linial, Nathan; Wigderson, Avi (2006), "Grafos expansores y sus aplicaciones", Bulletin of the American Mathematical Society , 43 (4): 439– 561, doi : 10.1090/S0273-0979-06-01126-8 , MR 2247919 En 2008, Linial y sus coautores ganaron el Premio Levi L. Conant de la Sociedad Matemática Estadounidense a la mejor exposición matemática por este artículo, un estudio sobre grafos expansores . ^{[ 1 ]}