Омер Рейнгольд

Омер Рейнгольд

עומר ריינגולד

 

Дата рождения

20 апреля 1969 года

Место рождения

Тель-Авив, Израиль

Омер Рейнгольд (Омер Рейнголд, Омер Рэйнгольд, англ. Omer Reingold, ивр. עומר ריינגולד) — израильский учёный в области информатики, профессор кафедры информатики Стэнфордского университета.

Биография

Омер Рейнгольд родился 20 апреля 1969 года в Тель-Авиве.

Вырос в Гиватаиме. Учился в школе Тельмы Еллин.

В 1991—1994 годах получил степень бакалавра по математике и информатике в Тель-Авивском университете, а через год продолжил изучение информатики.

В 1994—1998 годах получил докторскую степень в области компьютерных наук в Институте Вейцмана под руководством Мони Наора.

Занимался постдокторскими исследованиями в Институте Вейцмана, работал в AT&T и в Институте перспективных исследований в Принстоне.

В 1997 году Мони Наор и Омер Рейнгольд, изучая Сеть Фейстеля, предложили упрощённый вариант конструкции Люби — Ракоффа, состоящий из четырёх раундов. В этом варианте в качестве первого и последнего раунда используются две попарно-независимые перестановки. Два средних раунда конструкции Наора — Рейнголда идентичны раундам в конструкции Люби — Ракоффа.

В 1999—2004 годах — сотрудник AT & T Labs, Florham Park, NJ и математик в Институте перспективных исследований в Принстоне, Нью-Джерси.

Вместе с Вадханом и Вигдерсоном ввёл Зигзаг-произведение. В 2002 году Рейнгольд, Салил Вадхан и Ави Вигдерсон показали простое явное комбинаторное конструирование экспандеров постоянной степени. Конструирование производится итеративно и требует в качестве базиса экспандер постоянной степени. На каждой итерации используется зигзаг-произведение для создания другого графа, чей размер увеличивается, но степень и распространение остаются неизменными. Повторение процесса позволяет создать произвольно большие экспандеры. В 2005 году Рейнгольд представил алгоритм решения задачи st-связности, использующий логарифмическое пространство памяти. Задача состоит в проверке, существует ли путь между двумя заданными вершинами ненаправленного графа. Алгоритм сильно опирается на зигзаг-произведение. Обобщённо, для решения ненаправленной задачи s-t связности в логарифмическом пространстве памяти исходный граф преобразуется с использованием комбинации произведения и зигзаг-произведения в регулярный граф постоянной степени с логарифмическим диаметром. Произведение увеличивает распространение (ввиду увеличения диаметра) за счёт увеличения степени, а зигзаг-произведение используется для уменьшения степени с сохранением распространения.

С января 2004 года по июнь 2015 года — профессор (с октября 2011 года — полный профессор) факультета математики и информатики института Вейцмана.

В 2005 году — лауреат премии имени Грейс Мюррей Хоппер.

В 2009 году — лауреат премии Гёделя — за зигзаг-произведение графов и нахождение логарифмического по памяти детерминированного алгоритма решения задачи неориентированной st-связности.

С июля 2009 года по ноябрь 2014 года — главный научный сотрудник Microsoft Research Silicon Valley, Mountain View, Калифорния, США.

В 2014 году — член Ассоциации вычислительной техники.

С февраля 2015 года по сентябрь 2016 года — главный инженер-исследователь Samsung Research America.

С сентября 2016 года — профессор компьютерных наук в Стэнфордском университете.

Труды

• Reingold, Omer (2008), "Undirected connectivity in log-space", Journal of the ACM, 55 (4): Article 17, 24.
• Omer Reingold, Salil Vadhan, Avi Wigderson Proc. 41st IEEE Symposium on Foundations of Computer Science (FOCS). — 2000. — С. 3—13.