Eric Allender, Vikraman Arvind, Meena Mahajan

The aim of this paper is to use formal power series techniques to

study the structure of small arithmetic complexity classes such as

GapNC^1 and GapL. More precisely, we apply the Kleene closure of

languages and the formal power series operations of inversion and

root ...
more >>>

Jui-Lin Lee

In this paper we give a direct proof of $N_0=N_0^\prime$, i.e., the equivalence of

uniform $NC^1$ based on different recursion principles: one is OR-AND complete

binary tree (in depth $\log n$) and the other is the recursion on notation with value

bounded in $[0,k]$ and $|x|(=n)$ many ...
more >>>

Eric Allender, Samir Datta, Sambuddha Roy

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

Eric Allender, David Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy

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

Pooya Hatami, William Hoza, Avishay Tal, Roei Tell

We present new constructions of pseudorandom generators (PRGs) for two of the most widely-studied non-uniform circuit classes in complexity theory. Our main result is a construction of the first non-trivial PRG for linear threshold (LTF) circuits of arbitrary constant depth and super-linear size. This PRG fools circuits with depth $d\in\mathbb{N}$ ... more >>>