Fellows Logic Open Seminar

Online Space Complexity

The notion of online space complexity, introduced by Karp in 1967, quantifies the amount of space required to solve a given problem using an online algorithm. In this talk, I will study alternating online algorithms, represented by alternating Turing machines which scan the input exactly once from left to right. In the first half, I will show a lower bound technique, and two applications of it. The first one shows that the polynomial hierarchy of is infinite, and the second is a lower bound on the of checking whether a natural number is prime. In the second half, I will discuss open problems and extensions to the stochastic setting.