Нати Линиал - Nati Linial
Натан (Нати) Линиал (родился в 1953 году в Хайфе , Израиль ) - израильский математик и ученый-компьютерщик , профессор Школы компьютерных наук и инженерии Рэйчел и Селим Бенин Еврейского университета в Иерусалиме , а также авторитетный исследователь ISI .
Линиал учился на бакалавриате в Технионе и получил докторскую степень в 1978 году в Еврейском университете под руководством Мики Перлес. Он был аспирантом Калифорнийского университета в Лос-Анджелесе, прежде чем вернуться в Еврейский университет в качестве преподавателя.
В 2012 году он стал членом Американского математического общества . В 2019 году он выиграл премию FOCS Test of Time Award за статью « Цепи постоянной глубины, преобразование Фурье и обучаемость », в соавторстве с Ишаем Мансуром и Ноамом Нисаном.
Избранные публикации
- Линиал, Нати (1992), "Локальность в алгоритмах распределенных графов", SIAM J. Comput. , 21 (1): 193-201, CiteSeerX 10.1.1.471.6378 , DOI : 10,1137 / 0221015. Работа была удостоена премии Дейкстры 2013 года . По словам призового комитета: «Эта статья оказала большое влияние на алгоритмы распределенной передачи сообщений. Она сосредоточила внимание на понятии локальности в распределенных вычислениях и подняла интересные вопросы, касающиеся уровня локальности различных распределенных задач с точки зрения их временной сложности в различных классах сетей. Для достижения этой цели в этой статье Линиал разработал модель, особенно подходящую для изучения локальности, которая игнорирует размеры сообщений, асинхронность и сбои. Эта чистая модель позволила исследователям изолировать эффекты локальности и изучить роль расстояний и окрестностей как теоретико-графовых понятий и их взаимосвязь с алгоритмическими проблемами и проблемами теории сложности в распределенных вычислениях ".
- Бородин, Аллан ; Линиал, Натан; Сакс, 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 и его соавторы выиграли Леви Л. Конант премию в Американском математическом обществе для лучшего математического описания для этой статьи, обзора на экспандере .