Израильский математик и учёный-компьютерщик.
Натан (Нати) Линиал (родился в 1953 году в Хайфе , Израиль ) [1] — израильский математик и специалист по информатике , профессор Школы компьютерных наук и инженерии имени Рахили и Селима Бенина в Еврейском университете в Иерусалиме [ 2] и часто цитируемый исследователь ISI . [3]
Линиал получил степень бакалавра в Технионе и получил докторскую степень в 1978 году в Еврейском университете под руководством Михи Перлеса. [1] [4] Он был аспирантом-исследователем в Калифорнийском университете в Лос-Анджелесе, прежде чем вернуться в Еврейский университет в качестве преподавателя. [1]
В 2012 году он стал членом Американского математического общества . [5] В 2019 году он выиграл премию FOCS Test of Time Award за статью « Контрольные схемы, преобразование Фурье и обучаемость », написанную в соавторстве с Ишаем Мансуром и Ноамом Нисаном . [6]
Избранные публикации
- Линиал, Нати (1992), «Локальность в алгоритмах распределенных графов», SIAM J. Comput. , 21 (1): 193–201, CiteSeerX 10.1.1.471.6378 , doi : 10.1137/0221015. Статья получила премию Дейкстры 2013 года . По словам комитета премии: «Эта статья оказала большое влияние на распределенные алгоритмы передачи сообщений. Она сосредоточила внимание на понятии локальности в распределенных вычислениях и подняла интересные вопросы, касающиеся уровня локальности различных распределенных задач с точки зрения их временной сложности в различных классах сетей. Для достижения этой цели в этой статье Линиал разработал модель, особенно подходящую для изучения локальности, которая игнорирует размеры сообщений, асинхронность и сбои. Эта чистая модель позволила исследователям изолировать эффекты локальности и изучить роли расстояний и окрестностей как теоретико-графовых понятий и их взаимосвязи с алгоритмическими и теоретико-сложностными проблемами в распределенных вычислениях». [7]
- Бородин, Аллан ; Линиал, Натан; Сакс, Майкл Э. (1992), «Оптимальный онлайн-алгоритм для метрической системы задач», J. ACM , 39 (4): 745–763, doi : 10.1145/146585.146588 , S2CID 18783826. В этой статье о конкурентном анализе онлайн-алгоритмов изучаются метрические системы задач , очень общая модель задач, где решения о том, как обслуживать последовательность запросов, должны приниматься без знания будущих запросов. В ней представлена модель метрической системы задач, описывается, как использовать ее для моделирования различных проблем планирования , и разрабатывается алгоритм, который во многих ситуациях может быть продемонстрирован для оптимальной работы.
- Линиал, Натан; Мансур, Ишай; Нисан, Ноам (1993), «Схемы постоянной глубины, преобразование Фурье и обучаемость», J. ACM , 40 (3): 607–620, doi : 10.1145/174130.174138 , S2CID 16978276Выполняя гармонический анализ функций в классе сложности AC 0 (класс, представляющий высокопараллелизуемые вычислительные задачи), Линиал и его соавторы показывают, что эти функции плохо ведут себя как генераторы псевдослучайных чисел , могут быть хорошо аппроксимированы полиномами и могут эффективно изучаться системами машинного обучения .
- Линиал, Натан; Лондон, Эран; Рабинович, Юрий (1995), «Геометрия графов и некоторые ее алгоритмические приложения», Combinatorica , 15 (2): 215–245, doi :10.1007/BF01200757, S2CID 5071936Самая цитируемая статья Линиала по данным Google scholar , в этой статье исследуются связи между проблемами теории графов, такими как задача о многопродуктовом потоке , и вложениями с малым искажением метрических пространств в пространства малой размерности, такими как заданные леммой Джонсона–Линденштрауса .
- Hoory, Shlomo; Linial, Nathan; Wigderson, Avi (2006), «Расширительные графы и их приложения», Bulletin of the American Mathematical Society , 43 (4): 439–561, doi : 10.1090/S0273-0979-06-01126-8 , MR 2247919. В 2008 году Линиал и его соавторы получили премию Леви Л. Конанта Американского математического общества за лучшее математическое изложение этой статьи, обзора графов-расширителей . [1]
Ссылки
- ^ abcd "Премия Конанта 2008 года" (PDF) , Извещения Американского математического общества , 55 (4): 491–493, 2008.
- ↑ Домашняя страница Линиала в Еврейском университете, получено 08.09.2010.
- ↑ ISI Web of Knowledge. Архивировано 19 мая 2007 г. на Wayback Machine , получено 08.09.2010.
- ^ Нати Линиал в проекте «Генеалогия математики»
- ↑ Список членов Американского математического общества, получен 27 января 2013 г.
- ^ «Лауреаты премии FOCS 2019».
- ^ Премия Эдсгера В. Дейкстры 2013 года в области распределенных вычислений
