Hierarchies of complexity classes

The Faculty of Informatics is pleased to announce a seminar given by Stathis Zachos

DATE: Monday, April 29th, 2013
PLACE: USI Università della Svizzera italiana, room A34, Red building (Via G. Buffi 13)
TIME: 15.30

ABSTRACT:
Computational Complexity theory deals with the classification of problems into classes of hardness called complexity classes. In Abstract Complexity (in contrast to Concrete Complexity) we define complexity classes according to general structural properties, 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 also randomness, oracles, interactivity, promise, advice, operators.
Inclusion and separation relations between complexity classes constitute central research goals and form some of the most important open questions in theory.
This research has led to definitions of scores of complexity classes, as well as 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:
Stathis K. Zachos is a theoretical computer scientist. Zachos received his PhD from the ETHZ in Mathematics (and Computer Science), 1978. He has held the posts of professor in Computer Science at UCSB, CUNY and NTUA and Adjunct professor at ETHZ. He has worked as a researcher at MIT and Brown-Boveri. He has published research papers in several areas of Computer Science. His work on Randomized Complexity Classes, Arthur Merlin Games, and Interactive Proof Systems has been very influential in proving important theorems and is cited in main textbooks 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 Christos 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.  He has guided more than twenty doctoral students and more than fifty M.Sc./Diploma students, many of whom hold positions in Universities and research centers worldwide.

HOST: Prof. Evanthia Papadopoulou