Preliminary PhD exam:
Space Hierarchy Results for Semantic Models

Abstract: We present space hierarchy theorems for semantic models of computation with advice. For example, we demonstrate a language computable by two-sided error randomized machines with one bit of advice that is not computable by two-sided error machines with O(log n) bits of advice by a machine running in slightly less space. We prove similar results for both one-sided and zero-sided error machines. The proof techniques come from a line of research culminating in time hierarchy theorems for semantic models with one bit of advice [B02, FS04, FST05, MP06]. However, many of the proofs are substantially different in the space setting, in some instances resulting in tighter results in the space setting than in the time setting. We also demonstrate that delayed diagonalization can be used to prove space hierarchy theorems with one bit of advice for any reasonable model of computation, and for nice space bounds between logarithmic and polynomial. We conclude with remarks on areas of potential future research (both related and unrelated to the present research).