For a permutation group $G$ acting on the set $\Omega$
we say that two strings $x,y\,:\,\Omega\to\boole$
are {\em $G$-isomorphic} if they are equivalent under
the action of $G$, \ie, if for some $\pi\in G$ we have
$x(i^{\pi})=y(i)$ for all $i\in\Omega$.
Cyclic Shift, Graph Isomorphism ... more >>>

In this paper we consider two refined questions regarding
the query complexity of testing graph properties
in the adjacency matrix model.
The first question refers to the relation between adaptive
and non-adaptive testers, whereas the second question refers to
testability within complexity that
is inversely proportional to ... more >>>

We observe that many important computational problems in NC^1 share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial size TC^0 circuits if and only if it has TC^0 circuits of size n^{1+\epsilon} for every \epsilon > 0 (counting the ... more >>>