Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR97-044 | 26th September 1997 00:00

Searching constant width mazes captures the AC^0 hierarchy

RSS-Feed




TR97-044
Authors: David Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum
Publication: 26th September 1997 16:23
Downloads: 2181
Keywords: 


Abstract:


We show that searching a width k maze is complete for \Pi_k, i.e., for
the k'th level of the AC^0 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.



ISSN 1433-8092 | Imprint