Searching Constant Width Mazes Captures the AC0 Hierarchy - Barrington, David A. Mix; Lu, Chi-Jen; Miltersen, Peter Bro; Skyum, Sven (BRICS Report Series, 1997)
We show that searching a width k maze is complete for Pi_k, i.e., for the k’th level of the AC0 hierarchy. Equivalently, st-connectivity for width k grid graphs is complete for Pi_k. As an application, we show that there is a data structure solving dynamic st-connectivity for constant width grid graphs with time bound O(log log n) per operation on a random access machine. The dynamic algorithm is derived from the parallel one in an indirect way using algebraic tools.