Graph Isomorphism is the prime example of a computational problem with a wide difference between the best known lower and upper bounds on its complexity. There is a significant gap between extant lower and upper bounds for planar graphs as well. We bridge the gap for this natural and important ... more >>>

A monotone planar circuit (MPC) is a Boolean circuit that can be embedded in a plane, and that has only AND and OR gates. Yang showed that the one-input-face monotone planar circuit value problem (MPCVP) is in NC^2, and Limaye et. al. improved the bound to $\LogCFL$. Barrington et. al. ... more >>>

We study the complexity of restricted versions of st-connectivity, which is the standard complete problem for NL. Grid graphs are a useful tool in this regard, since * reachability on grid graphs is logspace-equivalent to reachability in general planar digraphs, and * reachability on certain classes of grid graphs gives ... more >>>

We investigate the s-t-connectivity problem for directed planar graphs, which is hard for L and is contained in NL but is not known to be complete. We show that this problem is logspace-reducible to its complement, and we show that the problem of searching graphs of genus 1 reduces to ... more >>>

We show that ACC^0 is precisely what can be computed with constant-width circuits of polynomial size and polylogarithmic genus. This extends a characterization given by Hansen, showing that planar constant-width circuits also characterize ACC^0. Thus polylogarithmic genus provides no additional computational power in this model. We consider other generalizations of ... more >>>

Constant-depth arithmetic circuits have been defined and studied in [AAD97,ABL98]; these circuits yield the function classes #AC^0 and GapAC^0. These function classes in turn provide new characterizations of the computational power of threshold circuits, and provide a link between the circuit classes AC^0 (where many lower bounds are known) and ... more >>>

Motivated by the question of how to define an analog of interactive proofs in the setting of logarithmic time- and space-bounded computation, we study complexity classes defined in terms of operators quantifying over oracles. We obtain new characterizations of $\NCe$, $\L$, $\NL$, $\NP$, and $\NSC$ (the nondeterministic version of SC). ... more >>>

Continuing a line of investigation that has studied the function classes #P, #SAC^1, #L, and #NC^1, we study the class of functions #AC^0. One way to define #AC^0 is as the class of functions computed by constant-depth polynomial-size arithmetic circuits of unbounded fan-in addition and multiplication gates. In contrast to ... more >>>