Бенджамин Россман - Википедия - Benjamin Rossman

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

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

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

Россман был Научный сотрудник Sloan на 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.
  • Демейн, Эрик Д.; Мозес, Шей; Россман, Бенджамин; Вейманн, Орен (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 г..
  • Россман, Бенджамин (2008). «Теоремы сохранения гомоморфизма». Журнал ACM. 55 (3): 1–53. Дои:10.1145/1379759.1379763.
  • Россман, Бенджамин (2008). «О постоянной глубине сложности k-клики». Материалы четырехдесятого ежегодного симпозиума ACM по теории вычислений - STOC 08. п. 721. Дои:10.1145/1374376.1374480. ISBN  9781605580470.
  • Россман, Бенджамин (2008). «Теоремы сохранения гомоморфизма». Журнал ACM. 55 (3): 1–53. Дои:10.1145/1379759.1379763.
  • Demaine, Erik D .; Мозес, Шей; Россман, Бенджамин; Вейманн, Орен (2009). «Оптимальный алгоритм декомпозиции для расстояния редактирования дерева». ACM-транзакции на алгоритмах. 6: 1–19. arXiv:cs / 0604037. Дои:10.1145/1644015.1644017.
  • Коппарты, Свастик; Россман, Бенджамин (2011). «Показатель доминирования гомоморфизма». Европейский журнал комбинаторики. 32 (7): 1097–1114. arXiv:1004.2485. Дои:10.1016 / j.ejc.2011.03.009.
  • Россман, Бенджамин; Servedio, Rocco A .; Тан, Ли-Ян (2015). "Теорема иерархии глубины среднего случая для булевых схем". 56-й ежегодный симпозиум IEEE по основам компьютерных наук, 2015 г.. С. 1030–1048. arXiv:1504.03398. Дои:10.1109 / FOCS.2015.67. ISBN  978-1-4673-8191-8.

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

  1. ^ "Бенджамин Россман, доцент кафедры математики и информатики". Университет Торонто.
  2. ^ а б "Бенджамин Россман, резюме" (PDF). Университет Торонто.
  3. ^ Бенджамин Э. Россман на Проект "Математическая генеалогия"
  4. ^ Россман, Бенджамин (2010). «Средняя сложность обнаружения клик (докторская диссертация, Массачусетский технологический институт)». HDL:1721.1/62441. Цитировать журнал требует | журнал = (помощь)
  5. ^ "Бенджамин Россман". Simons Institute for theory of theory of Computing, U.C. Кампус Беркли.
  6. ^ а б «Лауреат премии Андре Айзенштадта по математике, Бен Россман (Университет Торонто)». Centre de Recherches Mathématiques.
  7. ^ Россман, Бенджамин (2019). «Нижние оценки изоморфизма подграфов». В Бояне, Сиракове; Де Соуза, Пауло Ней; Виана, Марсело (ред.). Труды Международного конгресса математиков (ICM 2018). т. 4. С. 3425–3446. Дои:10.1142/9789813272880_0187. ISBN  978-981-327-287-3. S2CID  19175568.

внешняя ссылка