Статис Захос

Статис К. Захос ( греч . Статис (Естафиос) Захос ; родился в 1947 году в Афинах) — математик, логик и учёный -теоретик в области информатики.

Биография

Захос получил докторскую степень по математике (и информатике) в ETHZ (Швейцарском федеральном технологическом институте Цюриха) в 1978 году. Он занимал должности профессора информатики в Калифорнийском университете Санта-Барбаре , Бруклинском колледже в Городского университета Нью-Йорк и Афинский национальный технический университет , адъюнкт-профессор ETHZ . Он работал исследователем в Массачусетском технологическом институте Браун -Бовери .

Статис опубликовал исследовательские работы в нескольких областях информатики. Его работа над рандомизированными классами сложности , ^[1]^[2] протоколы Артура-Мерлина , ^[3] и интерактивные системы доказательств ^[4] оказал большое влияние на доказательство важных теорем и цитируется в основных учебниках по вычислительной сложности . ^[5]^[6]^[7] Один из его важных вкладов, использующих интерактивные системы доказательств и вероятностные кванторы, заключается в том, что проблема изоморфизма графов вряд ли будет NP-полной (совместно с Р. Боппаной, Дж. Хастадом). ^[8] Изоморфизм графов - одна из очень немногих знаменитых проблем в NP, NP-полнота которых еще не была доказана, или в самой влиятельной работе П. Захоса было введение и доказательство свойств класса Parity-P (совместно с Христосом Пападимитриу ). ^[9] Он также ввел вероятностные кванторы и их варианты для единообразного описания различных классов сложности, а также интерактивные системы доказательств и вероятностные игры. ^[10]

Его текущие интересы включают вероятностные и функциональные классы сложности , комбинаторные алгебры как основу теории вычислений , взаимосвязь криптографических методов и вычислительной сложности , а также алгоритмы для задач на графах . Он был соорганизатором международных конференций: STOC '87 (и программного комитета STOC '01), ICALP , CiE ( Вычислимость в Европе ), PLS, ASL ( Ассоциация символической логики ), Европейской летней встречи, ACAC (Афинский коллоквиум по алгоритмам и Сложность) и NYCAC (Нью-Йоркский коллоквиум по алгоритмам и сложности).

Он брат физика-теоретика Космаса Захоса .

См. также

Список греческих математиков

Ссылки

^ Захос, Статис (1982). «Надежность вероятностных классов вычислительной сложности при дефиниционных возмущениях». Информация и контроль . 54 (3): 143–154. дои : 10.1016/s0019-9958(82)80019-3 .
^ Захос, Статис; Ганс Хеллер (1986). «Решающая характеристика БПП» . Информация и контроль . 69 (1–3): 125–135. дои : 10.1016/s0019-9958(86)80044-4 .
^ Захос, Статис; Мартин Фюрер (1987). «Вероятностные квантификаторы против недоверчивых противников». Основы программных технологий и теоретической информатики . Конспекты лекций по информатике. Том. 287. стр. 443–455. дои : 10.1007/3-540-18625-5_67 . ISBN 978-3-540-18625-0 .
^ Фюрер, Мартин; Одед Гольдрейх; Ишай Мансур; Майкл Сипсер; Статис Захос (1989). «О полноте и корректности интерактивных систем доказательств». Достижения в области компьютерных исследований: случайность и вычисления . 5 : 25–32. CiteSeerX 10.1.1.39.9412 .
^ Пападимитриу, Христос Х. (1994). Вычислительная сложность . Эддисон Уэсли.
^ Хемаспаандра, Лейн А.; Мицунори Огихара (2001). Путеводитель по теории сложности . Спрингер. ISBN 978-3540674191 .
^ Ду, Дин-Чжу; Кер-И Ко (2000). Теория вычислительной сложности . Уайли-Интерсайенс.
^ Боппана, Рави Б.; Хастад, Йохан; Захос, Статис (6 мая 1987 г.). «Есть ли у co-NP короткие интерактивные доказательства?». Письма об обработке информации . 25 (2): 127–132. дои : 10.1016/0020-0190(87)90232-8 .
^ Пападимитриу, Христос Х.; Статис Захос (1982). «Два замечания о силе счета». Теоретическая информатика . Конспекты лекций по информатике. Том. 145. стр. 269–276. doi : 10.1007/BFb0009651 (неактивен 22 июня 2024 г.). ISBN 978-3-540-11973-9 . {{cite book}}: |journal= игнорируется ( справка ) CS1 maint: DOI неактивен по состоянию на июнь 2024 г. ( ссылка )
^ Захос, Статис (1988). «Вероятностные кванторы и игры». Журнал компьютерных и системных наук . 36 (3): 433–451. дои : 10.1016/0022-0000(88)90037-2 .

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

Профиль в Афинском национальном техническом университете

[1] Захос, Статис (1982). «Надежность вероятностных классов вычислительной сложности при дефиниционных возмущениях». Информация и контроль . 54 (3): 143–154. дои : 10.1016/s0019-9958(82)80019-3 .

[2] Захос, Статис; Ганс Хеллер (1986). «Решающая характеристика БПП» . Информация и контроль . 69 (1–3): 125–135. дои : 10.1016/s0019-9958(86)80044-4 .

[3] Захос, Статис; Мартин Фюрер (1987). «Вероятностные квантификаторы против недоверчивых противников». Основы программных технологий и теоретической информатики . Конспекты лекций по информатике. Том. 287. стр. 443–455. дои : 10.1007/3-540-18625-5_67 . ISBN 978-3-540-18625-0 .

[4] Фюрер, Мартин; Одед Гольдрейх; Ишай Мансур; Майкл Сипсер; Статис Захос (1989). «О полноте и корректности интерактивных систем доказательств». Достижения в области компьютерных исследований: случайность и вычисления . 5 : 25–32. CiteSeerX 10.1.1.39.9412 .

[5] Пападимитриу, Христос Х. (1994). Вычислительная сложность . Эддисон Уэсли.

[6] Хемаспаандра, Лейн А.; Мицунори Огихара (2001). Путеводитель по теории сложности . Спрингер. ISBN 978-3540674191 .

[7] Ду, Дин-Чжу; Кер-И Ко (2000). Теория вычислительной сложности . Уайли-Интерсайенс.

[8] Боппана, Рави Б.; Хастад, Йохан; Захос, Статис (6 мая 1987 г.). «Есть ли у co-NP короткие интерактивные доказательства?». Письма об обработке информации . 25 (2): 127–132. дои : 10.1016/0020-0190(87)90232-8 .

[9] Пападимитриу, Христос Х.; Статис Захос (1982). «Два замечания о силе счета». Теоретическая информатика . Конспекты лекций по информатике. Том. 145. стр. 269–276. doi : 10.1007/BFb0009651 (неактивен 22 июня 2024 г.). ISBN 978-3-540-11973-9 . {{cite book}}: |journal= игнорируется ( справка ) CS1 maint: DOI неактивен по состоянию на июнь 2024 г. ( ссылка )

[10] Захос, Статис (1988). «Вероятностные кванторы и игры». Журнал компьютерных и системных наук . 36 (3): 433–451. дои : 10.1016/0022-0000(88)90037-2 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]