Basser Seminar Series

Two remarks about logspace

Speaker: Taso Viglas
The School of IT, University of Sydney

Time: Wednesday 5 November 2008, 4-5pm

Location: The University of Sydney, School of IT Building, Lecture Theatre (Room 123), Level 1

Abstract

One of the main goals of computational complexity theory is to understand and classify practical (as well as not-so-practical) problems according to the computational resources that are required for their solution. If we are given specific limits for the amount and type of computational resources available (such as time, memory space and randomness) then some problems will be impossible to solve. The notion of a complexity class is often defined in terms of such computational limits, and is used to define groups of problems that have similar computational requirements. The class logspace for example, includes all problems that can be solved using only a small amount of memory space (logarithmic in the size of the input).

In this talk we discuss the problem of complexity class separations, and present an algorithmic approach that can be used to argue about complexity class separations around logspace. We show a connection between hardness and class separations, and present two new results related to methods for separating logspace from NP, which is a fundamental open problem in structural complexity theory.

Speaker's biography

Taso Viglas received his PhD from Princeton University in 2002. He was a postoctoral 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.