Time-space lower bounds for undirected and directed st-connectivity on jag models (1993).

Content Provider	CiteSeerX
Researcher	Edmonds, Jeff A.
Abstract	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...
File Format	PDF
Publisher Date	1993-01-01
Access Restriction	Open
Subject Keyword	Directed St-connectivity Time-space Lower Bound Jag Model Time-space Tradeoff Bounded Space Undirected Case Second Result Tight Bound Third Result Important Problem Undirected St-connectivity New Entropy Technique Upper Bound Jumping Automaton First Result
Content Type	Text
Resource Type	Thesis