Уильям Гасарх - William Gasarch

Уильям Ян Гасарх
Родился1959 (60–61 лет)
НациональностьСоединенные Штаты
Альма-матерУниверситет Стоуни-Брук
Гарвардский университет
ИзвестенТеория вычислительной сложности, Теория вычислимости, Теория вычислительного обучения, Теория Рэмси
Научная карьера
ПоляИнформатика
УчрежденияУниверситет Мэриленда, Колледж-Парк
ДокторантГарри Р. Льюис
Интернет сайтwww.cs.umd.edu/ ~ газарх
http://blog.computationalcomplexity.org/

Уильям Ян Гасарх (родился в 1959 г.[1]) - компьютерный ученый, известный своей работой в теория сложности вычислений, теория вычислимости, теория вычислительного обучения, и Теория Рамсея. В настоящее время он профессор Университет Мэриленда Кафедра компьютерных наук с отделением по математике.

По состоянию на 2015 год он руководил исследовательскими проектами более 40 старшеклассников,[нужна цитата ] в том числе Джейкоб Лурье. Он ведет совместный блог о вычислительной сложности с Лэнс Фортноу с 2007 года. Он был редактором рецензии на ACM SIGACT NEWS с 1997 по 2015 год, прежде чем уйти в отставку и передать эту работу Фреду Грину, профессору компьютерных наук в Университете Кларка.

Образование

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

Работа

Гасарх стал соучредителем (с Ричардом Бейгелем) области ограниченных запросов в теории рекурсии.[3] и написал много статей в этой области, увенчанных книгой по этой теме в соавторстве с Джорджией Мартин под названием Ограниченные запросы в теории рекурсии.[4] Он опубликовал такие книги, как Проблемы с точкой,[5] книга с широким взглядом на математику и теоретическую информатику, в соавторстве с Клайд Краскал и включает работы других профессоров, таких как Дэвид Эппштейн.[6] Он также стал соучредителем подполя теоретико-рекурсивного индуктивного вывода, названного Обучение через запросы[7] с участием Карл Смит. В последнее время он больше занимался комбинаторикой, в частности теорией Рэмси.[8][9][10] Он написал два обзора того, что теоретики думают о P против NP проблема.[11][12]

Блог

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

использованная литература

  1. ^ "Все еще типизирующий из Дагштуля". Журнал вычислительной сложности. Лэнс Фортноу и Уильям Гасарх. Получено 27 сентября 2018.
  2. ^ Уильям Гасарх на Проект "Математическая генеалогия"
  3. ^ http://www.cs.umd.edu/~gasarch/papers/gems.pdf Драгоценные камни в области ограниченных запросов Уильям Гасарх, 2003 г.
  4. ^ https://www.springer.com/us/book/9780817639662 Ограниченные запросы в теории рекурсии (совместно с Джорджией Мартин), Биркхаузер, 1999.
  5. ^ https://www.worldscientific.com/worldscibooks/10.1142/11261 Задачи с точным изучением математики и информатики, 2019
  6. ^ https://www.worldscientific.com/doi/abs/10.1142/9789813279735_0014 Глава 14: Слишком ли сложна эта задача для соревнований по математике в старших классах? 2019
  7. ^ http://www.cs.umd.edu/~gasarch/papers/lvqsur.pdf Обзор индуктивного вывода с упором на запросы, Gasarch and Smith, 1997
  8. ^ Гасарх, Уильям; Haeupler, Бернхард (2011). "Нижние границы чисел Ван дер Вардена: рандомизированные и детерминированные конструктивные". Электронный журнал комбинаторики. 18 (64). arXiv:1005.3749. Дои:10.37236/551.
  9. ^ Гасарх, Уильям; Haeupler, Бернхард (2010). «Раскраска сеток без прямоугольников». arXiv:1005.3750 [math.CO ].
  10. ^ Гасарх, Уильям; Haeupler, Бернхард (2011). «Программы доказательства заканчиваются с использованием порядков скважин, теории Рамсея и матриц». arXiv:1108.3347 [math.CO ].
  11. ^ http://www.cs.umd.edu/~gasarch/papers/poll.pdf P =? NP Poll, Уильям Гасарх, гостевая колонка в SIGACT NEWS Complexity Theory Column 36, 2002
  12. ^ http://www.cs.umd.edu/~gasarch/papers/poll2012.pdf Второй опрос P =? NP, Уильям Гасарх, гостевая колонка в SIGACT NEWS Complexity THeory Column 74, 2012
  13. ^ http://blog.computationalcomplexity.org/ Журнал вычислительной сложности

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