stringtranslate.com

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

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

Газарч часто выступает в качестве наставника в исследовательских проектах школьников старших классов; один из проектов, совместный с Джейкобом Лури , выиграл в 1996 году конкурс талантов Westinghouse Science Talent Search for Lurie. [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. ^ "Rectangle Free Colorings – William Gasarch". YouTube . 8 мая 2017 г. . Получено 12 октября 2022 г. .
  2. ^ "Still Typecasting from Dagstuhl". Computational Complexity Weblog . Лэнс Фортнау и Уильям Гасарч . Получено 27 сентября 2018 г.
  3. ^ Конвей, Джон Х.; Джексон, Аллин (июль 1996 г.). «Подающий надежды математик побеждает в конкурсе Вестингауза» (PDF) . Уведомления Американского математического общества . Получено 26 сентября 2016 г.
  4. ^ Уильям Гасарч в проекте «Генеалогия математики»
  5. ^ Гасарч, Уильям (16 марта 2023 г.). "Curriculum vitae" (PDF) . U. Maryland Computer Science . Получено 2024-02-14 .
  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 . doi : 10.37236/551. S2CID  534179.
  12. ^ Газарч, Уильям; Хойплер, Бернхард (2010). «Раскраска сеток без прямоугольников». arXiv : 1005.3750 [math.CO].
  13. ^ Газарч, Уильям; Хойплер, Бернхард (2011). «Программы доказательства завершаются с использованием хороших порядков, теории Рамсея и матриц». arXiv : 1108.3347 [math.CO].
  14. ^ Хемаспандра, Лейн А. (2002-06-01). "SIGACT news difficulty theory column 36". ACM SIGACT News . 33 (2): 34–47. doi :10.1145/564585.564599. ISSN  0163-5700. S2CID  36828694.
  15. ^ Хемаспандра, Лейн А. (11.06.2012). "SIGACT news difficulty theory column 74". ACM SIGACT News . 43 (2): 51–52. doi :10.1145/2261417.2261433. ISSN  0163-5700. S2CID  52847337.
  16. ^ Гасарч, Уильям И. (13.03.2019). «Гостевая колонка: Третий опрос P=?NP». ACM SIGACT News . 50 (1): 38–59. doi :10.1145/3319627.3319636. ISSN  0163-5700. S2CID  83458626.
  17. ^ Гасарх, Уильям; Метц, Эрик; Принц, Якоб; Смоляк, Дэниел (28 мая 2020 г.). Математические кусочки кексов: никто не хочет маленький кусочек. World Scientific. ISBN 978-981-12-1519-3.
  18. ^ http://blog.computationalcomplexity.org/ Веблог о вычислительной сложности

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