CS Colloquium on September 8 at 11am

Title: Combinatory Complexity: Operators on Complexity Classes

Speaker: Stathis Zachos, NTUA and CUNY
         http://www-old.ece.ntua.gr/acstaff/zachos.html

Date: September 8 (Monday)
Time: 11am 
Place: MCS 135

Abstract:

Operators form a powerful tool that has been used to describe complexity
classes, mainly those related to nondeterministic and probabilistic
polynomial time Turing machines. Here we introduce new operators: the
neutral operator "E", the complement operator "co" and the symmetric
operator "Delta". We show that many polynomial time complexity classes can
be described by using these operators combined with other known
operators. We investigate properties of operators when applied to
complexity classes and to other operators. We thus develop a calculus of
operators which offers new alternative, insightful descriptions of class
inclusions and helps in proving new complexity theoretic results and in
simplifying existing proofs of important theorems.

Biography of the Speaker:

(to be added)

Host: George Kollios (http://www.cs.bu.edu/~gkollios)