The Sum of Square Roots (SSR) problem is the following computational problem: Given positive integers $a_1, \dots, a_k$, and signs $\delta_1, \dots, \delta_k \in \{-1, 1\}$, check if $\sum_{i=1}^k \delta_i \sqrt{a_i} > 0$. The problem is known to have a polynomial time algorithm on the real RAM model of computation, ... more >>>

In this paper, we study the circuit value problem for monotone Boolean circuits (that is, circuits without negation gates) when the circuits are embedded on a surface of bounded genus, and all inputs to the circuits lie on at most constantly many faces. We show that this problem can be ... more >>>

We investigate the complexity of languages that correspond to algebraic real numbers, and we present improved upper bounds on the complexity of these languages. Our key technical contribution is the presentation of improved uniform TC^0 circuits
for division, matrix powering, and related problems, where the improvement is in terms of ... more >>>

We present an algorithm for constructing a depth-first search tree in planar digraphs; the algorithm can be implemented in the complexity class UL, which is contained in nondeterministic logspace NL, which in turn lies in NC^2. Prior to this (for more than a quarter-century), the fastest uniform deterministic parallel algorithm ... more >>>

A catalytic Turing machine is a model of computation that is created by equipping a Turing machine with an additional auxiliary tape which is initially filled with arbitrary content; the machine can read or write on auxiliary tape during the computation but when it halts auxiliary tape’s initial content must ... more >>>

We provide new upper bounds on the complexity of the s-t-connectivity problem in planar graphs, thereby providing additional evidence that this problem is not complete for NL. This also yields a new upper bound on the complexity of computing edit distance. Building on these techniques, we provide new upper bounds ... more >>>

We present improved uniform TC$^0$ circuits for division, matrix powering, and related problems, where the improvement is in terms of ``majority depth'' (initially studied by Maciel and Therien). As a corollary, we obtain improved bounds on the complexity of certain problems involving arithmetic circuits, which are known to lie in ... more >>>

We provide a uniform framework for proving the collapse of the hierarchy, $NC^1(\mathcal{C})$
for an exact arithmetic class $\mathcal{C}$ of polynomial degree. These hierarchies collapses all the way down to the third level of the ${AC}^0$-hierarchy, ${AC^0_3}(\mathcal{C})$. Our main collapsing exhibits are the classes \[\mathcal{C} \in \{{C}_={NC^1}, {C}_={L}, {C}_={SAC^1}, {C}_={P}\}.\]
more >>>

In this paper we initiate the study of proof systems where verification of proofs proceeds by NC0 circuits. We investigate the question which languages admit proof systems in this very restricted model. Formulated alternatively, we ask which languages can be enumerated by NC0 functions. Our results show that the answer ... more >>>

Planarity Testing is the problem of determining whether a given graph is planar while planar embedding is the corresponding construction problem.
The bounded space complexity of these problems has been determined to be Logspace by Allender and Mahajan with the aid of Reingold's result . Unfortunately, the algorithm is quite ... more >>>

We prove that Perfect Matching in bipartite planar graphs is in UL, improving upon
the previous bound of SPL (see [DKR10]) on its space complexity. We also exhibit space
complexity bounds for some related problems. Summarizing, we show that, constructing:
1. a Perfect Matching in bipartite planar graphs is in ... more >>>

The class NC$^1$ of problems solvable by bounded fan-in circuit families of logarithmic depth is known to be contained in logarithmic space L, but not much about the converse is known. In this paper we examine the structure of classes in between NC$^1$ and L based on counting functions or, ... more >>>

We investigate the space complexity of certain perfect matching
problems over bipartite graphs embedded on surfaces of constant genus
(orientable or non-orientable). We show that the problems of deciding
whether such graphs have (1) a perfect matching or not and (2) a
unique perfect matching or not, are in the ... more >>>

Graph isomorphism is an important and widely studied computational problem, with
a yet unsettled complexity.
However, the exact complexity is known for isomorphism of various classes of
graphs. Recently [DLN$^+$09] proved that planar graph isomorphism is complete for log-space.
We extend this result of [DLN$^+$09] further
to the ... more >>>

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