Натан (Нати) Linial (родился 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]
- Бородин, Аллан ; Линиал, Натан; Сакс, Michael E. (1992), "Алгоритм оптимальной на линии для метрической системы задач", Ж. 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 , в этой статье исследуются связи между теоретико-графическими проблемами, такими как проблема многопродуктовых потоков, и вложениями метрических пространств с низким уровнем искажений в пространства малой размерности, такие как те, которые задаются леммой Джонсона – Линденштрауса. .
- Хори, Шломо; Линиал, Натан; Wigderson, Avi (2006), "графы расширители и их приложения", Бюллетень Американского математического общества , 43 (4): 439-561, DOI : 10,1090 / S0273-0979-06-01126-8 , MR 2247919. В 2008 годе Linial и его соавторы выиграли Леви Л. Конант премию в Американском математическом обществе для лучшего математического описания для этой статьи, обзора на экспандере . [1]
Рекомендации
- ^ а б в г «Премия Конанта 2008 г.» (PDF) , Уведомления Американского математического общества , 55 (4): 491–493, 2008 г..
- ^ Домашняя страница Linial в в Еврейском университете , извлекаться 2010-09-08.
- ↑ ISI Web of Knowledge. Архивировано 19 мая 2007 г. на Wayback Machine , получено 8 сентября 2010 г.
- ^ Нати Линиал в проекте « Математическая генеалогия»
- ^ Список членов Американского математического общества , получено 27 января 2013 г.
- ^ «Победители премии FOCS 2019» .
- ^ 2013 Премия Эдсжера В. Дейкстры в области распределенных вычислений