Nati Linial

Matemático e informático israelí

Nathan (Nati) Linial (nacido en 1953 en Haifa , Israel ) ^[1] es un matemático e informático israelí , profesor en la Escuela de Ingeniería y Ciencias de la Computación Rachel y Selim Benin de la Universidad Hebrea de Jerusalén , ^[2] y un Investigador altamente citado del ISI . ^[3]

Linial realizó sus estudios universitarios en el Technion y recibió 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 de la facultad. ^[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]

Publicaciones Seleccionadas

• 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. Se centró en 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 los tamaños de los mensajes, la asincronía y las fallas. Este modelo limpio permitió a los investigadores aislar los efectos de la localidad y estudiar. el papel de las distancias y las vecindades, como nociones de 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 en línea óptimo para un sistema de tareas métrico", 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étricos , un modelo muy general de tareas en el que las decisiones sobre cómo atender una secuencia de solicitudes deben tomarse sin conocimiento de solicitudes futuras. Presenta el modelo del sistema métrico de tareas, describe cómo usarlo para modelar varios problemas de programación y desarrolla un algoritmo que, en muchas situaciones, puede demostrarse que funciona de manera óptima.
• Linial, Nathan; Mansur, 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. Al realizar un análisis armónico de funciones en la clase de complejidad AC 0 (una clase que representa problemas computacionales altamente paralelizables ), Linial y sus coautores muestran que estas funciones se comportan mal como generadores de números pseudoaleatorios , se pueden aproximar bien mediante polinomios y se pueden aprender. eficientemente mediante sistemas de aprendizaje automático .
• Linial, Nathan; Londres, Eran; Rabinovich, Yuri (1995), "La geometría de los gráficos 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 , este artículo explora las conexiones entre problemas de teoría de grafos, como el problema del flujo de múltiples productos , y las incorporaciones de baja distorsión de espacios métricos en espacios de baja dimensión, como los dados por el lema de Johnson-Lindenstrauss. .
• Hoory, Shlomo; Linial, Nathan; Wigderson, Avi (2006), "Gráficos de expansión y sus aplicaciones", Boletín de la Sociedad Estadounidense de Matemáticas , 43 (4): 439–561, doi : 10.1090/S0273-0979-06-01126-8 , SEÑOR  2247919. En 2008, Linial y sus coautores ganaron el premio Levi L. Conant de la Sociedad Estadounidense de Matemáticas a la mejor exposición matemática por este artículo, una encuesta sobre gráficos de expansión . ^[1]

Referencias

1. "Premio Conant 2008" (PDF) , Avisos de la Sociedad Matemática Estadounidense , 55 (4): 491–493, 2008.
2. Página de inicio de Linial en la Universidad Hebrea, consultado el 8 de septiembre de 2010.
3. ISI Web of Knowledge Archivado el 19 de mayo de 2007 en Wayback Machine , consultado el 8 de septiembre de 2010.
4. Nati Linial en el Proyecto Genealogía de Matemáticas
5. Lista de miembros de la Sociedad Estadounidense de Matemáticas, consultado el 27 de enero de 2013.
6. "Ganadores del premio FOCS 2019".
7. Premio Edsger W. Dijkstra 2013 en Computación Distribuida