ColloquiaSanthanam/MS Presentation/5-8-01

[Margaret Jaffey]

This is an announcement of Rahul Santhanam's Master's Presentation.

Date:	Tuesday, May 8, 2001

Time:	1:00 p.m.

Place:	Ryerson 277

M.S. Candidate:	Rahul Santhanam

M.S. Paper Title:	Relationships among Time and Space Complexity Classes

Abstract:

Multitape Turing machines are the canonical mathematical model for
studying the time and space requirements of problems. Most computational
problems that are efficient in practice have
efficient algorithms on multitape Turing machines, and vice versa.

We survey the literature on relationships among time and space
classes defined using multitape Turing machines. We discuss the result of
Paul, Hopcroft and Valiant that deterministic space T is more powerful
than deterministic time T and the result of Paul, Pippenger, Szemeredi and
Trotter that nondeterministic linear time is more powerful than
deterministic linear time. We also discuss techniques to simulate Turing
machines by Turing machines with different sets of resources, and
techniques to diagonalize against complexity classes, with specific
reference to the recent research by Fortnow et al. on time-space tradeoffs
for the Satisfiability problem. Finally, we mention a few results on
models other than Turing machines and resources other than time and space,
and list the major open problems in this area.

Mr. Santhanam's Advisor:  Prof. Janos Simon

A draft copy of Mr. Santhanam's M.S. paper will be available for 
review in Ry 161A.

Margaret
-- 
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margaret P. Jaffey			margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 161A)		(773) 702-6011
The University of Chicago		http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=