In this talk we discuss problems of complexity class separations and their connection to explicit hardness bounds and algorithmic design problems. Although typically a complexity class separation suggests the need for a lower bound, it is easy to see that (strong enough) upper bounds or algorithms can also be used to establish class separations. We will outline an algorithmic approach that can be used to argue about complexity class separations, especially around logspace: We describe some interesting connections between hardness and class separations, and present results related to methods for separating logspace from NP.

Date:	08:50-09:30, Thursday, March 26, 2009

Venue:	FIT Building 1-315, Tsinghua University

Title:	On Class Separations around Logspace

Speaker:	Anastasios Viglas

Biography:	Taso Viglas received his PhD from Princeton University in 2002. He was a postoctoral research fellow at the University of Toronto for two years, before joining the University of Sydney in July 2004. Taso's main research interests include computational complexity theory and algorithmic game theory.

Abstract:	In this talk we discuss problems of complexity class separations and their connection to explicit hardness bounds and algorithmic design problems. Although typically a complexity class separation suggests the need for a lower bound, it is easy to see that (strong enough) upper bounds or algorithms can also be used to establish class separations. We will outline an algorithmic approach that can be used to argue about complexity class separations, especially around logspace: We describe some interesting connections between hardness and class separations, and present results related to methods for separating logspace from NP.