LFCS Theory Seminar
Room 2511, JCMB, King's Buildings
2pm, Friday 23rd January 1998

(* NOTE NONSTANDARD DAY AND TIME *)

Title: Searching constant width mazes captures the $\mathrm{AC}^0$-hierarchy

Speaker: Sven Skyum (BRICS, University of Aarhus, Denmark)

Abstract: We show that searching a width $k$ maze is complete for~$\Pi_k$, i.e, the $k$th level of the $\mathrm{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.

(Joint work with David A. Mix Barrington, Chi-Jen Lu and Peter Bro Miltersen)

[Editor's note: ``$\mathrm{AC}^0$'' is the class of languages that are recognised by polynomial size, constant depth circuits; the ``$k$th level of the $\mathrm{AC}^0$ hierarchy'' is the restriction of $\mathrm{AC}^0$ to a specific depth~$k$.]