View source for On Solving Big Mazes Using Small Space

Solving mazes is a computational problem appearing in a wide range of situations - starting from puzzles, social networks and system verification applications. The fundamental abstraction of this problem is the graph reachability problem which asks if given a graph G and two special vertices s and t, is t reachable from s or not? The question of whether or not this problem can be solved using space that is logarithmic in the number of vertices, encapsulates the centre stage of space complexity theory. The problem captures the famous NL vs L problem in complexity theory. Designing unambiguously non-deterministic algorithms that use small space are important stepping stones in this direction.
This talk aims to motivate and give an overview of the ideas on this frontier. It will present some of our recent contributions and current research efforts.