Нати Линиал - Nati Linial

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

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

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

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

  • Линиал, Нати (1992), "Локальность в алгоритмах распределенных графов", SIAM J. Comput., 21 (1): 193–201, CiteSeerX  10.1.1.471.6378, Дои:10.1137/0221015. Работа победила в конкурсе 2013 г. Премия Дейкстры. По словам призового комитета: «Эта статья оказала большое влияние на алгоритмы распределенной передачи сообщений. Она сосредоточила внимание на понятии локальности в распределенных вычислениях и подняла интересные вопросы, касающиеся уровня локальности различных распределенных задач с точки зрения их временной сложности в различных классах сетей. Для достижения этой цели в этой статье Линиал разработал модель, особенно подходящую для изучения локальности, которая игнорирует размер сообщений, асинхронность и сбои. Эта чистая модель позволила исследователям изолировать влияние локальности и изучить роль расстояний и окрестностей как теоретико-графовых понятий и их взаимосвязь с алгоритмическими и теоретико-сложными проблемами в распределенных вычислениях ".[7]
  • Бородин, Аллан; Линиал, Натан; Сакс, Майкл Э. (1992), «Оптимальный онлайн-алгоритм для метрической системы задач», J. ACM, 39 (4): 745–763, Дои:10.1145/146585.146588. Эта статья о Конкурентный анализ из онлайн-алгоритмы исследования метрические системы задач, очень общая модель задач, в которой решения о том, как обслуживать последовательность запросов, должны приниматься без знания будущих запросов. Он знакомит с метрической моделью системы задач, описывает, как ее использовать для моделирования различных планирование задач, и разрабатывает алгоритм, который во многих ситуациях может работать оптимально.
  • Линиал, Натан; Мансур, Ишай; Нисан, Ноам (1993), "Схемы постоянной глубины, преобразование Фурье и обучаемость", J. ACM, 40 (3): 607–620, Дои:10.1145/174130.174138. Выполняя гармонический анализ по функциям в класс сложности AC0 (класс, представляющий высоко параллелизируемый вычислительные задачи), Линиал и его соавторы показывают, что эти функции плохо себя ведут при генераторы псевдослучайных чисел, хорошо аппроксимируется многочлены, и можно эффективно изучить машинное обучение системы.
  • Линиал, Натан; Лондон, Эран; Рабинович, Юрий (1995), "Геометрия графов и некоторые ее алгоритмические приложения", Комбинаторика, 15 (2): 215–245, Дои:10.1007 / BF01200757. Наиболее цитируемая статья Линиала по версии Google ученый, в этой статье исследуются связи между задачами теории графов, такими как проблема многопродуктового потока и вложения с низким уровнем искажений метрические пространства в низкоразмерные пространства, такие как заданные Лемма Джонсона – Линденштрауса.
  • Хори, Шломо; Линиал, Натан; Вигдерсон, Ави (2006), «Графы-расширители и их приложения», Бюллетень Американского математического общества, 43 (4): 439–561, Дои:10.1090 / S0273-0979-06-01126-8, МИСТЕР  2247919. В 2008 году Линиал и его соавторы выиграли Премия Леви Л. Конанта из Американское математическое общество для лучшего математического изложения этой статьи, обзор по графики расширения.[1]

Рекомендации

  1. ^ а б c d «Приз Конанта 2008» (PDF), Уведомления Американского математического общества, 55 (4): 491–493, 2008.
  2. ^ Домашняя страница Линиала в Еврейском университете, получено 8 сентября 2010.
  3. ^ Сеть знаний ISI В архиве 19 мая 2007 г. Wayback Machine, получено 8 сентября 2010.
  4. ^ Нати Линиал на Проект "Математическая генеалогия"
  5. ^ Список членов Американского математического общества, получено 27 января 2013.
  6. ^ «Лауреаты премии FOCS 2019».
  7. ^ Премия Эдсжера В. Дейкстры в области распределенных вычислений, 2013 г.