Нати Линиал

Натан (Нати) Линиал (родился в 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 года. По словам призового комитета: «Эта статья оказала большое влияние на алгоритмы распределенной передачи сообщений. Она сосредоточила внимание на понятии локальности в распределенных вычислениях и подняла интересные вопросы, касающиеся уровня локальности различных распределенных задач с точки зрения их временной сложности в различных классах сетей. Для достижения этой цели в этой статье Линиал разработал модель, особенно подходящую для изучения локальности, которая игнорирует размер сообщений, асинхронность и сбои. Эта чистая модель позволила исследователям изолировать влияние локальности и изучить роль расстояний и окрестностей как теоретико-графовых понятий и их взаимосвязь с алгоритмическими проблемами и проблемами теории сложности в распределенных вычислениях ».
• Бородин, Аллан ; Линиал, Натан; Сакс, Майкл Э. (1992), «Оптимальный онлайн-алгоритм для метрической системы задач», J. ACM, 39 (4): 745–763, DOI : 10.1145 / 146585.146588. В этой статье по конкурентному анализу онлайн-алгоритмов изучается система метрических задач, очень общая модель задач, в которой необходимо принимать решения о том, как обслуживать последовательность запросов. без знания будущих запросов. Он вводит метрическую модель системы задач, описывает, как ее использовать для моделирования различных задач планирования, и разрабатывает алгоритм, который во многих ситуациях может работать оптимально.
• Линиал, Натан; Мансур, Ишай; Нисан, Ноам (1993), «Схемы постоянной глубины, преобразование Фурье и обучаемость», J. ACM, 40 (3): 607–620, doi : 10.1145 / 174130.174138. Выполняя гармонический анализ функций в классе сложности AC (класс, представляющий высоко распараллеливаемые вычислительные проблемы), Линиал и его соавторы показывают, что эти функции плохо себя ведут. как генераторы псевдослучайных чисел, могут быть хорошо аппроксимированы полиномами и могут быть эффективно изучены с помощью систем машинного обучения.
• Linial, Nathan; Лондон, Эран; Рабинович, Юрий (1995), «Геометрия графов и некоторые из ее алгоритмических приложений», Combinatorica, 15 (2): 215–245, doi : 10.1007 / BF01200757. Наиболее цитируемая статья Линиала по мнению ученого Google, в этой статье исследуются связи между проблемами теории графов, такими как проблема многопродуктового потока, и встраиваниями метрических пространств с низким уровнем искажений. в низкоразмерные пространства, такие как те, что заданы леммой Джонсона – Линденштрауса.
• Хори, Шломо; Линиал, Натан; Вигдерсон, Ави (2006), «Графы-расширители и их приложения», Бюллетень Американского математического общества, 43 (4): 439–561, doi : 10.1090 / S0273-0979-06-01126-8, MR 2247919. В 2008 году Линиал и его соавторы выиграли приз Леви Л. Конанта от Американского математического общества за лучшее математическое изложение этой статьи, обзор расширяющих графов.