Бенджамин Россман
Бенджамин Э. Россман — американский математик и учёный-теоретик в области информатики, специализирующийся на теории сложности вычислений . [1] В настоящее время он является доцентом кафедры информатики и математики в Университете Дьюка .
Биография
[ редактировать ]Он окончил Пенсильванский университет со степенью бакалавра в 2001 году и магистратуры в 2002 году. [2] В 2011 году он получил докторскую степень. с консультантом Мадху Суданом из Массачусетского технологического института с диссертацией «Сложность обнаружения клик в среднем случае» . [3] [4] С 2010 по 2013 год Россман был постдоком в Токийском технологическом институте . С 2013 по 2016 год он был доцентом Каварабаяши проекта больших графов Национального института информатики . В 2014–2015 учебном году он был научным сотрудником Саймонса-Беркли в Институте теории вычислений Саймонса . он был доцентом кафедры математики и информатики Университета Торонто До начала 2019 года , прежде чем присоединиться к Университету Дьюка . [2] Осенью 2018 года он был приглашенным учёным в Институте теории вычислений Саймонса. [5]
Его исследования направлены на количественную оценку минимальных ресурсов, необходимых для решения основных проблем в комбинаторных моделях, таких как булевы схемы . С помощью творческих методов, основанных на логике и вероятностном методе, Бен получил революционные нижние границы сложности обнаружения клик и определения связности в случайных графах . Среди других его заметных результатов — теоремы об иерархии размеров и глубины для схем ограниченной глубины , которые отвечают на давние вопросы. [6]
Россман был научным сотрудником Слоана в 2017–2018 учебном году. он выиграл премию Айзенштадта . В 2018 году [6] Он был приглашенным докладчиком на Международном конгрессе математиков в 2018 году в Рио-де-Жанейро . [7]
Избранные публикации
[ редактировать ]- Гуревич Юрий ; Россман, Бенджамин; Шульте, Вольфрам (2005). «Семантическая сущность AsmL». Теоретическая информатика . 343 (3): 370–412. дои : 10.1016/j.tcs.2005.06.017 .
- Россман, Б. (2005). «Экзистенциальные положительные типы и сохранение при гомоморфизмах». 20-й ежегодный симпозиум IEEE по логике в информатике (LICS'05) . стр. 467–476. дои : 10.1109/LICS.2005.16 . ISBN 0-7695-2266-1 . S2CID 18553513 .
- Демейн, Эрик Д .; Мозес, Шей; Россман, Бенджамин; Вейманн, Орен (2007). «Оптимальный алгоритм декомпозиции для расстояния редактирования дерева». Автоматы, языки и программирование . Конспекты лекций по информатике. Том. 4596. стр. 146–157. дои : 10.1007/978-3-540-73420-8_15 . ISBN 978-3-540-73419-2 .
- Бласс, Андреас ; Гуревич Юрий; Розенцвейг, декан; Россман, Бенджамин (2007). «Интерактивные алгоритмы малых шагов II: абстрактные автоматы и теорема о характеризации». Логические методы в информатике . 3 (4). arXiv : 0707.3789 . дои : 10.2168/LMCS-3(4:4)2007 . S2CID 99659 .
- Россман, Бенджамин (2008). «Теоремы сохранения гомоморфизма». Журнал АКМ . 55 (3): 1–53. дои : 10.1145/1379759.1379763 . S2CID 306577 .
- Россман, Бенджамин (2008). «О сложности k-клики постоянной глубины». Материалы сорокового ежегодного симпозиума ACM по теории вычислений - STOC 08 . стр. 721–730. дои : 10.1145/1374376.1374480 . ISBN 9781605580470 . S2CID 9362397 .
- Демейн, Эрик Д.; Мозес, Шей; Россман, Бенджамин; Вейманн, Орен (2009). «Оптимальный алгоритм декомпозиции расстояния редактирования дерева». Транзакции ACM на алгоритмах . 6 :1–19. arXiv : cs/0604037 . дои : 10.1145/1644015.1644017 . S2CID 7878119 .
- Коппартия, Свастик; Россман, Бенджамин (2011). «Показатель доминирования гомоморфизма». Европейский журнал комбинаторики . 32 (7): 1097–1114. arXiv : 1004.2485 . дои : 10.1016/j.ejc.2011.03.009 . S2CID 6624366 .
- Россман, Бенджамин; Серведио, Рокко А.; Тан, Ли-Ян (2015). «Теорема об иерархии глубины в среднем случае для логических схем». 56-й ежегодный симпозиум IEEE по основам информатики , 2015 г. стр. 1030–1048. arXiv : 1504.03398 . дои : 10.1109/FOCS.2015.67 . ISBN 978-1-4673-8191-8 . S2CID 7722713 .
Ссылки
[ редактировать ]- ^ «Бенджамин Россман, доцент кафедры компьютерных наук» . Университет Дьюка .
- ^ Jump up to: а б «Бенджамин Россман, резюме» (PDF) . Университет Торонто .
- ^ Бенджамин Э. Россман в проекте «Математическая генеалогия»
- ^ Россман, Бенджамин (2010). Средняя сложность обнаружения клик (Докторская диссертация, Массачусетский технологический институт) (Диссертация). Массачусетский технологический институт. hdl : 1721.1/62441 .
- ^ «Бенджамин Россман» . Институт теории вычислений Саймонса, кампус Калифорнийского университета в Беркли . 11 апреля 2014 г.
- ^ Jump up to: а б «Получатель премии Андре Айзенштадта 2018 года по математике, Бен Россман (Университет Торонто)» . Центр математических исследований .
- ^ Россман, Бенджамин (2019). «Нижние оценки изоморфизма подграфов» . В Боян, Сираков; Де Соуза, Пауло Ней; Виана, Марсело (ред.). Материалы Международного конгресса математиков (ICM 2018) . Том. 4. С. 3425–3446. дои : 10.1142/9789813272880_0187 . ISBN 978-981-327-287-3 . S2CID 19175568 .
Внешние ссылки
[ редактировать ]- «Нижние оценки изоморфизма подграфов - Бенджамин Россман - ICM2018» . Веб-сайт ICM2018 в Рио = YouTube.
- «Полиномиальное время без выбора — Бен Россман» . Ютуб . Институт перспективных исследований.
- 1980 рождений
- Живые люди
- Американские ученые-компьютерщики
- Американские ученые-теоретики-компьютерщики
- Американские математики XX века
- Американские математики XXI века
- Канадские математики XX века
- Канадские математики XXI века
- Выпускники Пенсильванского университета
- Выпускники Массачусетского технологического института
- Академический состав Университета Торонто
- Слоанские научные сотрудники