David Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum

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 ...
more >>>

Max Bannach, Zacharias Heinrich, RĂ¼diger Reischuk, Till Tantau

Computing kernels for the hitting set problem (the problem of

finding a size-$k$ set that intersects each hyperedge of a

hypergraph) is a well-studied computational problem. For hypergraphs

with $m$ hyperedges, each of size at most~$d$, the best algorithms

can compute kernels of size $O(k^d)$ in ...
more >>>