Статис Захос - Stathis Zachos

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

биография

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

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

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

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

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

Рекомендации

  1. ^ Захос, Статис (1982). «Устойчивость классов вероятностной вычислительной сложности к дефиниционным возмущениям». Информация и контроль. 54 (3): 143–154. Дои:10.1016 / с0019-9958 (82) 80019-3.
  2. ^ Захос, Статис; Ганс Хеллер (1986). «Решающая характеристика БПП». Информация и контроль. 69 (1–3): 125–135. Дои:10.1016 / с0019-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. ^ Hemaspaandra, Lane A .; Мицунори Огихара (2001). Компаньон по теории сложности. Springer. ISBN  978-3540674191.
  7. ^ Ду, Дин-Чжу; Кер-И Ко (2000). Теория вычислительной сложности. Wiley-Interscience.
  8. ^ Боппана, Рави Б .; Хастад, Йохан; Захос, Статис (6 мая 1987 г.). «Есть ли у co-NP короткие интерактивные доказательства?». Письма об обработке информации. 25 (2): 127–132. Дои:10.1016/0020-0190(87)90232-8.
  9. ^ Papadimitriou, Christos H .; Статис Захос (1982). «Два замечания о силе счета». В материалах 6-й GI-конференции по теоретической информатике. Конспект лекций по информатике. 145: 269–276. Дои:10.1007 / BFb0009651. ISBN  978-3-540-11973-9.
  10. ^ Захос, Статис (1988). «Вероятностные кванторы и игры». Журнал компьютерных и системных наук. 36 (3): 433–451. Дои:10.1016/0022-0000(88)90037-2.

внешняя ссылка