Time-Space Lower Bounds for Undirected and Directed ST-Connectivity on JAG Models

Directed and undirected st-connectivity are important problems in computing. There are algorithms for the undirected case that use O (n) time and algorithms that use O (log n) space. The first result of this thesis proves that, in a very natural structured model, the JAG (Jumping Automata for Graphs), these upper bounds are not simultaneously achievable. This uses new entropy techniques to prove tight bounds on a game involving a helper and a player that models a computation having precomputed information about the input stored in its bounded space. The second result proves that a JAG requires a time-space tradeoff of T \Theta S 1 2 2\Omega i mn 1 2 j to compute directed st-connectivity. The third result proves a time-space tradeoff of T \Theta S 1 3 2\Omega i m 2 3 n 2 3 j on a version of the..