Омер Рейнгольд
Омер Рейнгольд (Омер Рейнголд, Омер Рэйнгольд, англ. Omer Reingold, ивр. עומר ריינגולד) — израильский учёный в области информатики, профессор кафедры информатики Стэнфордского университета[1].
Биография[править]
Омер Рейнгольд родился 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.
Примечания[править]
- Родившиеся 20 апреля
- Родившиеся в 1969 году
- Персоналии по алфавиту
- Родившиеся в Тель-Авиве
- Учёные по алфавиту
- Выпускники Тель-Авивского университета
- Выпускники института Вейцмана
- Фелло Ассоциации вычислительной техники
- Лауреаты премии Гёделя
- Лауреаты премии имени Грейс Мюррей Хоппер
- Учёные в области информатики Израиля
- Публицисты Израиля
- Профессора Стэнфордского университета
- Евреи в США
- Сабра
- Ашкеназы
- Евреи-математики
- AT&T
- Профессора института Вейцмана
- Сотрудники Microsoft
- Математики Израиля
- Израильтяне в США