Matemático y científico informático israelí
Nathan (Nati) Linial (nacido en 1953 en Haifa , Israel ) [1] es un matemático y científico 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] y un investigador altamente citado por el ISI . [3]
Linial realizó sus estudios universitarios en el Technion y recibió su doctorado en 1978 de la Universidad Hebrea bajo la supervisión de Micha Perles. [1] [4] Fue investigador de posgrado en la Universidad de California en Los Ángeles antes de regresar a la Universidad Hebrea como miembro de la facultad. [1]
En 2012 se convirtió en miembro de la American Mathematical Society . [5] En 2019 ganó el premio FOCS Test of Time por el artículo " Constant Depth Circuits, Fourier Transform, and Learnability ", en coautoría con Yishay Mansour y Noam Nisan . [6]
Publicaciones seleccionadas
- Linial, Nati (1992), "Localidad en algoritmos de grafos distribuidos", SIAM J. Comput. , 21 (1): 193–201, CiteSeerX 10.1.1.471.6378 , doi :10.1137/0221015El 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 el foco 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 los fallos. Este modelo limpio permitió a los investigadores aislar los efectos de la localidad y estudiar los roles de las distancias y los vecindarios, 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 el sistema de tareas métricas", J. ACM , 39 (4): 745–763, doi : 10.1145/146585.146588 , S2CID 18783826Este artículo sobre el análisis competitivo de algoritmos en línea estudia los sistemas de tareas métricas , un modelo muy general de tareas en el que las decisiones sobre cómo atender una secuencia de solicitudes deben tomarse sin conocer las solicitudes futuras. Presenta el modelo de sistema de tareas métricas, describe cómo usarlo para modelar varios problemas de programación y desarrolla un algoritmo que puede demostrar que funciona de manera óptima en muchas situaciones.
- 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 16978276Al realizar un análisis armónico en funciones de 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 de manera eficiente mediante 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 5071936El 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 incrustaciones 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 expansores y sus aplicaciones", Boletín de la Sociedad Matemática Americana , 43 (4): 439–561, doi : 10.1090/S0273-0979-06-01126-8 , MR 2247919En 2008, Linial y sus coautores ganaron el Premio Levi L. Conant de la Sociedad Matemática Americana a la mejor exposición matemática por este artículo, una encuesta sobre gráficos expansores . [1]
Referencias
- ^ abcd "Premio Conant 2008" (PDF) , Avisos de la Sociedad Matemática Americana , 55 (4): 491–493, 2008.
- ^ Página de inicio de Linial en la Universidad Hebrea, consultada el 8 de septiembre de 2010.
- ^ ISI Web of Knowledge Archivado el 19 de mayo de 2007 en Wayback Machine , consultado el 8 de septiembre de 2010.
- ^ Nati Linial en el Proyecto de Genealogía Matemática
- ^ Lista de miembros de la American Mathematical Society, consultado el 27 de enero de 2013.
- ^ "Ganadores del premio FOCS 2019".
- ^ Premio Edsger W. Dijkstra 2013 en Computación Distribuida