Нати Линиал

Натан (Нати) Линиал
Рожденный	1953 Хайфа, Израиль
Альма-матер	Технион – Израильский технологический институт , Еврейский университет в Иерусалиме
Известный	Схемы постоянной глубины, преобразование Фурье, обучаемость
Награды	Член Американского математического общества (2012 г.), премия FOCS Test of Time (2019 г.)
Научная карьера
Поля	Математика, Информатика
Учреждения	Еврейский университет Иерусалима
Докторантура	Миша Перлс

Натан (Нати) Линиал (родился в 1953 году в Хайфе , Израиль ) — израильский математик и ученый-компьютерщик , профессор Школы компьютерных наук и инженерии Рэйчел и Селима Бенин при Еврейском университете в Иерусалиме , и высоко цитируемый исследователь ISI .

Линиал учился на бакалавриате в Технионе и получил степень доктора философии в 1978 году в Еврейском университете под руководством Миши Перлеса. Он был аспирантом Калифорнийского университета в Лос-Анджелесе, прежде чем вернуться в Еврейский университет в качестве преподавателя.

В 2012 году он стал членом Американского математического общества . В 2019 году он выиграл премию FOCS Test of Time за статью « Цепи постоянной глубины, преобразование Фурье и обучаемость », написанную в соавторстве с Ишаем Мансуром и Ноамом Нисаном .

Избранные публикации

• Линиал, Нати (1992), «Локальность в алгоритмах распределенных графов», SIAM J. Comput. , 21 (1): 193–201, CiteSeerX   10.1.1.471.6378 , doi : 10.1137/0221015 . Статья выиграла премию Дейкстры в 2013 году . По словам комитета премии: «Эта статья оказала большое влияние на распределенные алгоритмы передачи сообщений. Она сосредоточила внимание на понятии локальности в распределенных вычислениях и подняла интересные вопросы, касающиеся уровня локальности различных распределенных задач с точки зрения Для достижения этой цели в этой статье Линиал разработал модель, особенно подходящую для изучения локальности, которая игнорирует размеры сообщений, асинхронность и сбои. Эта чистая модель позволила исследователям изолировать эффекты локальности и изучения. роль расстояний и окрестностей как понятий теории графов, а также их взаимосвязь с алгоритмическими и теоретико-сложными задачами в распределенных вычислениях».
• Бородин, Аллан ; Линиал, Натан; Сакс, Майкл Э. (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 ⁰ (класс, представляющий вычислительные задачи с высокой степенью распараллеливания ), Линиал и его соавторы показывают, что эти функции плохо ведут себя как генераторы псевдослучайных чисел , могут хорошо аппроксимироваться полиномами и могут эффективно обучаться системами машинного обучения .
• Линиал, Натан; Лондон, Эран; Рабинович, Юрий (1995), «Геометрия графов и некоторые ее алгоритмические приложения», Combinatorica , 15 (2): 215–245, doi : 10.1007/BF01200757 , S2CID   5071936 . Самая цитируемая статья Линиала по мнению ученого Google . В этой статье исследуются связи между проблемами теории графов, такими как проблема многотоварного потока с низкими искажениями , и вложениями метрических пространств в низкоразмерные пространства, такие как те, которые заданы леммой Джонсона – Линденштрауса. .
• Хори, Шломо; Линиал, Натан; Вигдерсон, Ави (2006), «Расширяющие графики и их приложения», Бюллетень Американского математического общества , 43 (4): 439–561, doi : 10.1090/S0273-0979-06-01126-8 , MR   2247919 . В 2008 году Линиал и его соавторы выиграли премию Леви Л. Конанта Американского математического общества за лучшее математическое изложение этой статьи — обзора графов-расширителей .