stringtranslate.com

Уильям Гасарч

Уильям Ян Гасарч ( / ɡ ə ˈ s ɑː r ʃ / gə- SARSH ; [1] родился в 1959 году [2] ) — американский учёный-компьютерщик, известный своими работами в области теории сложности вычислений , теории вычислимости , теории вычислительного обучения и теории Рамсея. . В настоящее время он является профессором факультета компьютерных наук Университета Мэриленда с дочерней должностью в области математики.

Гасарч часто выступает наставником исследовательских проектов старшеклассников; один из них, с Джейкобом Лурье , выиграл конкурс научных талантов Westinghouse в 1996 году для Лурье. [3] С 2007 года он вел блог о сложности вычислений вместе с Лэнсом Фортноу. С 1997 по 2015 год он был редактором рецензий на книги в ACM SIGACT NEWS.

Образование

Гасарч получил докторскую степень по информатике в Гарварде в 1985 году по рекомендации Гарри Р. Льюиса . Его диссертация называлась « Теоретико-рекурсивные методы в теории сложности и комбинаторике» . [4] Осенью 1985 года он был нанят на постоянную профессорскую должность в Университете Мэриленда. В 1991 году он получил должность доцента с постоянным стажем, а в 1998 году — до профессора. [5]

Работа

Гасарч стал соучредителем (вместе с Ричардом Бейгелем) области ограниченных запросов в теории рекурсии [6] и написал множество статей в этой области, завершающимися книгой по этой теме, написанной в соавторстве с Джорджией Мартин, под названием « Ограниченные запросы в теории рекурсии» . [7] Он опубликовал такие книги, как « Проблемы с точкой» , [8] книгу с широким взглядом на математику и теоретическую информатику, которую он написал в соавторстве с Клайдом Краскалом и включает работы других профессоров, таких как Дэвид Эппштейн . [9] Он также стал соучредителем направления теоретико-рекурсивного индуктивного вывода под названием « Обучение через запросы» [10] вместе с Карлом Смитом . В последнее время он больше занимался комбинаторикой, особенно теорией Рамсея. [11] [12] [13] Он написал три обзора того, что теоретики думают о проблеме P и NP : в 2002, 2012 и 2019 годах. [14] [15] [16] В 2020 году он написал «Математические кусочки кексов»: Никто не хочет маленького кусочка с Эриком Метцем, Джейкобом Принцем и Дэниелом Смоляком. [17]

Блог

Лэнс Фортноу начал вести блог по теоретической информатике с упором на теорию сложности в 2002 году. [18] Гасарч был частым гостем блоггера до 2007 года, когда он стал официальным со-блогером.

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

  1. ^ «Раскраски без прямоугольников - Уильям Гасарч» . YouTube . 8 мая 2017 г. Проверено 12 октября 2022 г.
  2. ^ "Все еще типизация от Дагштула" . Блог о вычислительной сложности . Лэнс Фортноу и Уильям Гасарч . Проверено 27 сентября 2018 г.
  3. ^ Конвей, Джон Х.; Джексон, Аллин (июль 1996 г.). «Начинающий математик выигрывает конкурс Вестингауза» (PDF) . Уведомления Американского математического общества . Проверено 26 сентября 2016 г.
  4. ^ Уильям Гасарч в проекте «Математическая генеалогия»
  5. ↑ Гасарч, Уильям (16 марта 2023 г.). «Биографическая справка» (PDF) . Информатика Университета Мэриленда . Проверено 14 февраля 2024 г.
  6. ^ http://www.cs.umd.edu/~gasarch/papers/gems.pdf «Жемчужины в области ограниченных запросов», Уильям Гасарч, 2003 г.
  7. ^ https://www.springer.com/us/book/9780817639662 Ограниченные запросы в теории рекурсии (совместно с Джорджией Мартин), Биркхаузер, 1999 г.
  8. ^ https://www.worldscientific.com/worldscibooks/10.1142/11261 Проблемы с точкой при изучении математики и информатики, 2019 г.
  9. ^ https://www.worldscientific.com/doi/abs/10.1142/9789813279735_0014 Глава 14: Слишком ли сложна эта задача для школьного соревнования по математике?, 2019
  10. ^ http://www.cs.umd.edu/~gasarch/papers/lvqsur.pdf Обзор индуктивного вывода с акцентом на запросы, Гасарч и Смит, 1997 г.
  11. ^ Гасарч, Уильям; Хойплер, Бернхард (2011). «Нижние границы чисел Ван дер Вардена: рандомизированный и детерминированный конструктив». Электронный журнал комбинаторики . 18 (64). arXiv : 1005.3749 . дои : 10.37236/551. S2CID  534179.
  12. ^ Гасарч, Уильям; Хёплер, Бернхард (2010). «Свободная раскраска сеток прямоугольной формы». arXiv : 1005.3750 [math.CO].
  13. ^ Гасарч, Уильям; Хёплер, Бернхард (2011). «Программы доказательства завершаются использованием упорядочения лунок, теории Рамсея и матриц». arXiv : 1108.3347 [math.CO].
  14. ^ Хемаспаандра, Лейн А. (1 июня 2002 г.). «Колонка 36 теории сложности новостей SIGACT» . Новости ACM SIGACT . 33 (2): 34–47. дои : 10.1145/564585.564599. ISSN  0163-5700. S2CID  36828694.
  15. ^ Хемаспаандра, Лейн А. (11 июня 2012 г.). «Колонка 74 теории сложности новостей SIGACT» . Новости ACM SIGACT . 43 (2): 51–52. дои : 10.1145/2261417.2261433. ISSN  0163-5700. S2CID  52847337.
  16. ^ Гасарч, Уильям И. (13 марта 2019 г.). «Колонка гостей: третий опрос P =?NP». Новости ACM SIGACT . 50 (1): 38–59. дои : 10.1145/3319627.3319636. ISSN  0163-5700. S2CID  83458626.
  17. ^ Гасарч, Уильям; Мец, Эрик; Принц, Джейкоб; Смоляк, Даниил (28 мая 2020 г.). Математические кусочки кексов: никто не хочет маленького кусочка. Всемирная научная. ISBN 978-981-12-1519-3.
  18. ^ http://blog.computationalcomplexity.org/ Блог о сложности вычислений

Внешние ссылки