All reports by Author David Mix Barrington:

__
TR05-149
| 7th December 2005
__

Eric Allender, David Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy#### Grid Graph Reachability Problems

Revisions: 1

__
TR01-033
| 27th April 2001
__

Eric Allender, David Mix Barrington, William Hesse#### Uniform Circuits for Division: Consequences and Problems

__
TR00-065
| 7th September 2000
__

Eric Allender, David Mix Barrington#### Uniform Circuits for Division: Consequences and Problems

Comments: 2

__
TR99-012
| 19th April 1999
__

Eric Allender, Andris Ambainis, David Mix Barrington, Samir Datta, Huong LeThanh#### Bounded Depth Arithmetic Circuits: Counting and Closure

Comments: 1

__
TR98-020
| 10th April 1998
__

Andris Ambainis, David Mix Barrington, Huong LeThanh#### On Counting $AC^0$ Circuits with Negative Constants

__
TR97-044
| 26th September 1997
__

David Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum#### Searching constant width mazes captures the AC^0 hierarchy

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

Eric Allender, David Mix Barrington, William Hesse

Integer division has been known to lie in P-uniform TC^0 since

the mid-1980's, and recently this was improved to DLOG-uniform

TC^0. At the time that the results in this paper were proved and

submitted for conference presentation, it was unknown whether division

lay in DLOGTIME-uniform TC^0 (also known as ...
more >>>

Eric Allender, David Mix Barrington

The essential idea in the fast parallel computation of division and

related problems is that of Chinese remainder representation

(CRR) -- storing a number in the form of its residues modulo many

small primes. Integer division provides one of the few natural

examples of problems for which ...
more >>>

Eric Allender, Andris Ambainis, David Mix Barrington, Samir Datta, Huong LeThanh

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

Andris Ambainis, David Mix Barrington, Huong LeThanh

Continuing the study of the relationship between $TC^0$,

$AC^0$ and arithmetic circuits, started by Agrawal et al.

(IEEE Conference on Computational Complexity'97),

we answer a few questions left open in this

paper. Our main result is that the classes Diff$AC^0$ and

Gap$AC^0$ ...
more >>>

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