Питер Гакс
Питер Гакс | |
|---|---|
| Рожденный | 9 мая 1947 г. Будапешт , Венгрия |
| Национальность | венгерский |
| Гражданство | Венгрия, США |
| Альма-матер | Университет Этвеша Лоранда Университет Гете во Франкфурте Стэнфордский университет |
| Известный | надежные клеточные автоматы, правило ГКЛ, колмогоровская сложность |
| Научная карьера | |
| Поля | вероятность, теория сложности, теория информации, клеточные автоматы |
| Учреждения | Венгерская академия наук Рочестерский университет Бостонский университет |
| Докторантура | Клаус Питер Шнорр |
Петер Гач (венгерское произношение: ['pe:ter 'ga:tʃ]; родился 9 мая 1947 года), профессионально также известный как Питер Гач , — венгерско - американский математик и ученый-компьютерщик, профессор и внешний член Венгерской Академия наук. Он хорошо известен своими работами в области надежных вычислений, случайности в вычислениях, алгоритмической сложности , алгоритмической вероятности и теории информации .
Карьера
[ редактировать ]Петер Гач учился в средней школе в своем родном городе, затем получил диплом (MS) в Университете Лоранда Этвёша в Будапеште в 1970 году. Гач начал свою карьеру в качестве исследователя в Институте прикладной математики Венгерской академии наук . [1] Он получил докторскую степень во Франкфуртском университете имени Гете в 1978 году. Во время учебы у него была возможность посещать Московский государственный университет и работать с Андреем Колмогоровым и его студентом Леонидом Левиным . До 1979 года он был приглашенным научным сотрудником в Стэнфордском университете . Он был доцентом Рочестерского университета с 1980 по 1984 год, а затем перешел в Бостонский университет , где получил должность в 1985 году. С 1992 года он был профессором. [2]
Работа
[ редактировать ]Гакс внес вклад во многие области информатики. Именно Гач и Ласло Ловас впервые представили метод эллипсоидов вниманию международного сообщества в августе 1979 года, опубликовав его доказательства и некоторые усовершенствования. [3] [4] [5] Гакс также внес вклад в теорему Зипсера – Лаутенмана . [6] Его основной вклад и исследования были сосредоточены на клеточных автоматах и колмогоровской сложности.
Работа над клеточными автоматами
[ редактировать ]Его наиболее важным вкладом в область клеточных автоматов, помимо правила ГКЛ (правило Гача – Курдюмова – Левина), является построение надежного одномерного клеточного автомата, представляющего, таким образом, контрпример к гипотезе о положительных ставках . [7] Конструкция, которую он предложил, многомасштабна и сложна. [8] Позже тот же метод был использован для построения апериодических наборов мозаики. [9]
Работа над алгоритмической теорией информации и колмогоровской сложностью
[ редактировать ]Гакс является автором нескольких важных статей в области алгоритмической теории информации и колмогоровской сложности . Вместе с Леонидом Левиным он установил основные свойства префиксной сложности, включая формулу сложности пар. [10] и для недостатков случайности, включая результат, заново открытый позже и теперь известный как лемма об обильном избытке . [11] [12] Он показал, что соответствие между сложностью и априорной вероятностью, которое справедливо для префиксной сложности, больше не верно для монотонной сложности и непрерывной априорной вероятности. [13] [14] В родственной теории алгоритмической случайности он доказал, что каждая последовательность сводится по Тьюрингу к случайной (результат, теперь известный как теорема Гача – Кучеры, поскольку он был независимо доказан Антонином Кучерой). [14] Позже он (с соавторами) ввёл понятие алгоритмической дистанции и доказал её связь с условной сложностью. [15] [14]
Он был одним из пионеров алгоритмической статистики. [16] представил одну из квантовых версий алгоритмической сложности, [17] изучил свойства алгоритмической случайности для общих пространств [18] [19] и общие классы мер. [20] Некоторые из этих результатов отражены в его обзорах по алгоритмической теории информации. [21] [22] Он также доказал результаты на границе между классической и алгоритмической теорией информации: плодотворный пример, показывающий разницу между общей и взаимной информацией (совместно с Яношем Кёрнером ). [23] Вместе с Рудольфом Альсведе и Кёрнером он доказал лемму о разрушении . [24]
Ссылки
[ редактировать ]- ^ «Список людей, работавших в Институте Реньи» . Институт математики Альфреда Реньи . Проверено 5 декабря 2020 г.
- ^ «Био» . Факультет компьютерных наук Бостонского университета . Проверено 5 декабря 2020 г.
- ^ Колата, Джина Бари (2 ноября 1979 г.). «Математики поражены открытием русских». Наука . 206 (4418): 545–546. Бибкод : 1979Sci...206..545B . дои : 10.1126/science.206.4418.545 . JSTOR 1749236 . ПМИД 17759415 .
- ^ Гач, Питер; Ловас, Ласло (1981), Кениг, Х.; Корте, Б.; Риттер, К. (ред.), «Алгоритм Хачияна для линейного программирования» , Mathematical Programming at Oberwolfach , vol. 14, Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 61–68, doi : 10.1007/bfb0120921 , ISBN 978-3-642-00805-4 , получено 27 ноября 2020 г.
- ^ Шенитцер, Эйб и Джон Стиллвелл, ред. Математическая эволюция . МАА, 2002.
- ^ Лаутеманн, Клеменс (8 ноября 1983 г.). «БПП и полиномиальная иерархия» . Письма об обработке информации . 17 (4): 215–217. дои : 10.1016/0020-0190(83)90044-3 . ISSN 0020-0190 .
- ^ Гач, Питер (1 апреля 2001 г.). «Надежные клеточные автоматы с самоорганизацией» . Журнал статистической физики . 103 (1): 45–267. arXiv : math/0003117 . Бибкод : 2001JSP...103...45G . дои : 10.1023/A:1004823720305 . ISSN 1572-9613 . S2CID 2434448 .
- ^ Грей, Лоуренс Ф. (1 апреля 2001 г.). «Путеводитель для читателей по статье Гакса о «положительных ставках»» . Журнал статистической физики . 103 (1): 1–44. Бибкод : 2001JSP...103....1G . дои : 10.1023/А:1004824203467 . ISSN 1572-9613 . S2CID 14256431 .
- ^ Дюран, Бруно; Ромащенко Андрей; Шен, Александр (01 мая 2012 г.). «Наборы плиток с фиксированной точкой и их применение» . Журнал компьютерных и системных наук . Памяти Амира Пнуэли. 78 (3): 731–764. arXiv : 0910.2415 . дои : 10.1016/j.jcss.2011.11.001 . ISSN 0022-0000 . S2CID 3024979 .
- ^ Peter Gacs. On the symmetry of algorithmic information. Doklady Akademii Nauk SSSR , 218(6):1265–1267, 1974. In Russian.
- ^ Питер Гакс. Точные выражения для некоторых тестов на случайность. З. Математика. Бревно. Грдл. М. , 26:385–394, 1980.
- ^ Дауни, Родни Г. и Денис Р. Хиршфельдт. Алгоритмическая случайность и сложность. Спрингер, 2010 г.
- ^ Питер Гакс. О связи между сложностью описания и алгоритмической вероятностью. Теоретическая информатика, 22:71–93, 1983. Краткая версия: Учеб. 22-еIEEE FOCS (1981) 296-303.
- ^ Jump up to: а б с Ли, Мин и Пол Витаньи. Введение в колмогоровскую сложность и ее приложения. Том. 3. Нью-Йорк: Спрингер, 2008.
- ^ Чарльз Х. Беннетт, Питер Гакс, Минг Ли, Пол М.Б. Витаньи и Войцих Зурек. Информационная дистанция. IEEE Transactions on Information Theory , 44(4):1407–1423, 1998. (Предварительная версия появилась в STOC'97, arXiv:1006.3520.) По данным Google Scholar, к апрелю 2021 года эта статья была процитирована 687 раз [1]
- ^ Питер Гакс, Джон Тромп и Пол М.Б. Витаньи. Алгоритмическая статистика. IEEE Transactions on Information Theory , 47:2443–2463, 2001. arXiv:math/0006233[math.PR]. Краткая версия с аналогичным названием в Algorithmic Learning Theory , LNCS 1968/2000.
- ^ Адити Дхагат, Питер Гач и Питер Винклер. Об игре в «двадцать вопросов» со лжецом. В материалах третьего ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , SODA'92, страницы 16–22, Филадельфия, Пенсильвания, США, 1992. Общество промышленной и прикладной математики.
- ^ Питер Гакс. Равномерный тест алгоритмической случайности в общем пространстве. Теоретическая информатика , 341(1-3):91–137, 2005.
- ^ Питер Гакс, Матье Уойруп и Кристобаль Рохас. Случайность в вычислимых вероятностных пространствах – динамическая точка зрения. Теория вычислительных систем , 48:465–485, 2011. 10.1007/s00224-010-9263-x, arXiv:0902.1939. Появился также вСТАКС 2009.
- ^ Лоран Бьенвеню, Питер Гакс, Матье Уойруп, Кристобаль Рохас и Александр Шен. Случайность по классу мер. Труды Математического института им. Стеклова , 274(1):34–89, 2011. На английском и русском языках, также в arXiv:1103.1529.
- ^ Питер Гакс. Конспекты лекций о сложности описания и случайности. Технический отчет, Бостонский университет, факультет компьютерных наук, Бостон, Массачусетс, 02215, 2009 г.www.cs.bu.edu/faculty/gacs/papers/ait-notes.pdf.
- ^ Томас М. Ковер, Питер Гакс и Роберт М. Грей. Вклад Колмогорова в теорию информации и сложность алгоритмов. Анналы вероятности , 17(3):840–865, 1989.
- ^ Питер Гач и Янош Корнер. Общая информация гораздо меньше взаимной информации. Проблемы управления и инф. Т., 2:149–162, 1973.
- ^ Альсведе, Гакс, Кёрнер. Границы условных вероятностей в приложениях в многопользовательском общении, З. Варш. и Verw Areas 34, 1976, 157–177 .
- 1947 рождений
- Живые люди
- Венгерские ученые-компьютерщики
- Американские ученые-компьютерщики
- Американские математики XX века
- Венгерские математики XX века
- Американские математики XXI века
- Венгерские математики XXI века
- Сотовые автоматы
- Теоретики информации
- Теоретики-компьютерщики
- Выпускники Франкфуртского университета Гете
- факультет Рочестерского университета
- Преподаватели Бостонского университета