Статис Захос

Греческий математик и логик (родился в 1947 году)

Статис К. Захос ( греч . Στάθης (Ευστάθιος) Ζάχος ; родился в 1947 году в Афинах) — математик, логик и ученый- теоретик в области информатики.

Биография

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

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

Его текущие интересы включают вероятностные и функциональные классы сложности , комбинаторные алгебры как основу теории вычислений , взаимосвязи криптографических методов и вычислительной сложности , а также алгоритмы для задач графов. Он был одним из организаторов международных конференций: STOC '87 (и программный комитет STOC '01), ICALP , CiE ( Computability in Europe ), PLS, ASL ( Association for Symbolic Logic ) European Summer Meeting, ACAC (Athens Colloquium on Algorithms and Complexity) и NYCAC (New York Colloquium on Algorithms and Complexity).

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

Смотрите также

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

Ссылки

^ Захос, Статис (1982). «Надежность вероятностных классов вычислительной сложности при дефиниционных возмущениях». Информация и управление . 54 (3): 143– 154. doi :10.1016/s0019-9958(82)80019-3.
^ Захос, Статис; Ганс Хеллер (1986). «Решающая характеристика BPP». Информация и управление . 69 ( 1– 3): 125– 135. doi : 10.1016/s0019-9958(86)80044-4 .
^ Zachos, Stathis; Martin Fürer (1987). «Вероятностные квантификаторы против недоверчивых противников». Основы технологии программного обеспечения и теоретической информатики . Конспект лекций по информатике. Том 287. С. 443– 455. doi :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 короткие интерактивные доказательства?». Information Processing Letters . 25 (2): 127– 132. doi :10.1016/0020-0190(87)90232-8.
^ Papadimitriou, Christos H.; Stathis Zachos (1982). «Два замечания о силе подсчета». Теоретическая информатика . Lecture Notes in Computer Science. Vol. 145. pp. 269– 276. doi :10.1007/BFb0009651 (неактивен 1 ноября 2024 г.). ISBN 978-3-540-11973-9. {{cite book}}: |journal=проигнорировано ( помощь )CS1 maint: DOI неактивен по состоянию на ноябрь 2024 г. ( ссылка )
^ Zachos, Stathis (1988). «Вероятностные квантификаторы и игры». Журнал компьютерных и системных наук . 36 (3): 433– 451. doi :10.1016/0022-0000(88)90037-2.

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

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

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

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

[3] Zachos, Stathis; Martin Fürer (1987). «Вероятностные квантификаторы против недоверчивых противников». Основы технологии программного обеспечения и теоретической информатики . Конспект лекций по информатике. Том 287. С. 443– 455. doi :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 короткие интерактивные доказательства?». Information Processing Letters . 25 (2): 127– 132. doi :10.1016/0020-0190(87)90232-8.

[9] Papadimitriou, Christos H.; Stathis Zachos (1982). «Два замечания о силе подсчета». Теоретическая информатика . Lecture Notes in Computer Science. Vol. 145. pp. 269– 276. doi :10.1007/BFb0009651 (неактивен 1 ноября 2024 г.). ISBN 978-3-540-11973-9. {{cite book}}: |journal=проигнорировано ( помощь )CS1 maint: DOI неактивен по состоянию на ноябрь 2024 г. ( ссылка )

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