Бенджамин Россман
американский математик

Бенджамин Э. Россман — американский математик и теоретик информатики, специализирующийся на теории сложности вычислений . [1] В настоящее время он является доцентом кафедры информатики и математики в Университете Дьюка .

Биография

Он окончил Пенсильванский университет со степенью бакалавра в 2001 году и магистра в 2002 году. [2] В 2011 году он получил степень доктора философии под руководством Мадху Судана из Массачусетского технологического института с диссертацией «Сложность обнаружения клик в среднем» . [3] [4] С 2010 по 2013 год Россман был постдоком в Токийском технологическом институте . С 2013 по 2016 год он был доцентом в проекте Kawarabayashi Large Graph Project Национального института информатики . В 2014–2015 учебном году он был научным сотрудником Simons-Berkeley в Институте Simons по теории вычислений . Он был доцентом на кафедрах математики и компьютерных наук Университета Торонто до начала 2019 года, прежде чем присоединиться к Университету Дьюка . [2] Осенью 2018 года он был приглашенным ученым в Институте теории вычислений Саймонса. [5]

Его исследования направлены на количественную оценку минимальных ресурсов, необходимых для решения основных проблем в комбинаторных моделях, таких как булевы схемы . С помощью творческих методов, основанных на логике и вероятностном методе, Бен вывел новаторские нижние границы сложности обнаружения клик и определения связности в случайных графах . Его другие заметные результаты включают теоремы об иерархии размера и глубины для схем с ограниченной глубиной , отвечающие на давние вопросы. [6]

Россман был научным сотрудником Sloan в учебном году 2017–2018. Он выиграл премию Айзенштадта в 2018 году . [6] Он был приглашенным докладчиком на Международном конгрессе математиков в 2018 году в Рио-де-Жанейро . [7]

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

  • Гуревич, Юрий ; Россман, Бенджамин; Шульте, Вольфрам (2005). «Семантическая сущность AsmL». Теоретическая информатика . 343 (3): 370–412. doi :10.1016/j.tcs.2005.06.017.
  • Россман, Б. (2005). «Экзистенциальные положительные типы и сохранение при гомоморфизмах». 20-й ежегодный симпозиум IEEE по логике в компьютерных науках (LICS' 05) . стр. 467–476. doi :10.1109/LICS.2005.16. ISBN 0-7695-2266-1. S2CID  18553513.
  • Demaine, Erik D .; Mozes, Shay; Rossman, Benjamin; Weimann, Oren (2007). "Оптимальный алгоритм разложения для расстояния редактирования дерева". Автоматы, языки и программирование . Конспект лекций по информатике. Том 4596. С. 146–157. doi :10.1007/978-3-540-73420-8_15. ISBN 978-3-540-73419-2.
  • Бласс, Андреас ; Гуревич, Юрий; Розенцвейг, Дин; Россман, Бенджамин (2007). "Интерактивные алгоритмы с малым шагом II: Абстрактные машины состояний и теорема о характеризации". Логические методы в информатике . 3 (4). arXiv : 0707.3789 . doi :10.2168/LMCS-3(4:4)2007. S2CID  99659.
  • Россман, Бенджамин (2008). «Теоремы сохранения гомоморфизма». Журнал ACM . 55 (3): 1–53. doi :10.1145/1379759.1379763. S2CID  306577.
  • Россман, Бенджамин (2008). "О постоянной глубине сложности k-клики". Труды сорокового ежегодного симпозиума ACM по теории вычислений - STOC 08. стр. 721–730. doi :10.1145/1374376.1374480. ISBN 9781605580470. S2CID  9362397.
  • Демейн, Эрик Д.; Мозес, Шей; Россман, Бенджамин; Вайман, Орен (2009). «Оптимальный алгоритм разложения для расстояния редактирования дерева». ACM Transactions on Algorithms . 6 : 1–19. arXiv : cs/0604037 . doi :10.1145/1644015.1644017. S2CID  7878119.
  • Коппарти, Свастик; Россман, Бенджамин (2011). «Экспонента доминирования гомоморфизма». Европейский журнал комбинаторики . 32 (7): 1097–1114. arXiv : 1004.2485 . doi : 10.1016/j.ejc.2011.03.009. S2CID  6624366.
  • Россман, Бенджамин; Серведио, Рокко А.; Тан, Ли-Янг (2015). «Теорема о глубине иерархии в среднем для булевых схем». 56-й ежегодный симпозиум IEEE по основам компьютерной науки 2015 г. стр. 1030–1048. arXiv : 1504.03398 . doi :10.1109/FOCS.2015.67. ISBN 978-1-4673-8191-8. S2CID  7722713.

Ссылки

  1. ^ "Бенджамин Россман, доцент кафедры компьютерных наук". Университет Дьюка .
  2. ^ ab "Бенджамин Россман, резюме" (PDF) . Университет Торонто .
  3. ^ Бенджамин Э. Россман в проекте «Генеалогия математики»
  4. ^ Россман, Бенджамин (2010). Средняя сложность обнаружения клик (Докторская диссертация, Массачусетский технологический институт) (Диссертация). Массачусетский технологический институт. hdl :1721.1/62441.
  5. ^ "Бенджамин Россман". Институт теории вычислений Саймонса, кампус Калифорнийского университета в Беркли . 11 апреля 2014 г.
  6. ^ ab «Получатель премии Андре Айзенштадта по математике 2018 года, Бен Россман (Университет Торонто)» . Центр математических исследований .
  7. ^ Россман, Бенджамин (2019). «Нижние оценки изоморфизма подграфов». В Boyan, Sirakov; De Souza, Paulo Ney; Viana, Marcelo (ред.). Труды Международного конгресса математиков (ICM 2018) . Том 4. стр. 3425–3446. doi :10.1142/9789813272880_0187. ISBN 978-981-327-287-3. S2CID  19175568.
  • «Нижние оценки изоморфизма подграфов – Бенджамин Россман – ICM2018». Rio ICM2018website=YouTube.
  • "Choiceless Polynomial Time - Ben Rossman". YouTube . Институт перспективных исследований.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Benjamin_Rossman&oldid=1222485183"