Colloquia, Seminars and Conference News
Title : Hierarchies of Complexity Classes
Date : October 2, 2007. (11:00 am) Tea starts half an hour before each seminar
Location: ITEB 336
Speaker : Prof. Stathis Zachos
Abstract:
Computational Complexity deals with the classification of problems into classes of hardness, called complexity classes. Complexity classes are defined by modifying structural parameters, such as the model of computation (Turing Machine, RAM, Finite Automaton, PDA, LBA, PRAM, Monotone Circuits), the mode of computation (deterministic, nondeterministic, probabilistic, alternating, uniform parallel), the kind of the automaton (Decider, Acceptor, Generator, Transducer, Counting), the resources (time, space, # of processors, circuit size and depth) and others: randomness, oracles, interactivity, promise, advice, operators. Some of the most important questions concern inclusion and separation relations among complexity classes. This line of research has led to numerous definitions of complexity classes, as well as inclusion sequences of classes known as "complexity hierarchies". We will review some of the most interesting ones, including the Polynomial-Time Hierarchy, a Counting Hierarchy and an Approximability Hierarchy.
Bio:Zachos received his PhD from the ETHZ (Swiss Federal Institute of Technology Zurich) in Mathematics (and Computer Science), 1978. He was a visiting scientist in MIT in 1982 and 1983. Zachos works on the area of Computational Complexity. One of his important contributions, using Interactive Proof Systems and Probabilistic Quantifiers, is that the Graph Isomorphism Problem is not likely to be NP-complete (joint with R. Boppana, J. Hastad). Graph Isomorphism is one of the very few celebrated problems in NP that have not been shown yet to be either NP-Complete or in P. Zachos's most influential work was introducing and proving properties of the class Parity-P (with C.
Papadimitriou). He also introduced Probabilistic Quantifiers and Alternations of Probabilistic Quantifiers to uniformly describe various Complexity Classes as well as Interactive Proof Systems and Probabilistic Games. His current interests include Probabilistic and Functional Complexity Classes, Combinatory Algebras as a foundation to Theory of Computations, the interconnections of Cryptographic Techniques and Computational Complexity as well as Algorithms for Graph Problems. Recently, he co-organized International Conferences in Greece, STOC, ICALP, PLS, in 2001 on Crete, ASL European Summer Meeting and PLS in 2005, ACAC (Athens Colloquium on Algorithms and
Complexity) in 2006, in Athens.
[Back]
