Publications of David A. Mix Barrington
- E. Allender, D.A.M. Barrington, T. Chakraborty, S. Datta, and S. Roy,
Planar and Grid Graph Reachability Problems, Theory of Computing Systems, to appear (special issue from Complexity 2006).
- D.A.M. Barrington, N. Immerman, C. Lautemann, N. Schweikardt, and D. Therien, First-Order Expressibility of Languages with Neutral Letters Or: The Crane
Beach Conjecture, Journal of Computer and System Sciences
70, (2005), 101-127.
- W. M. Hesse, E. Allender, and D.A.M. Barrington, Uniform Constant-Depth Threshold Circuits for Division and Iterated Multiplication, Journal of Computer and System Sciences 62:4 (2002), 695-716.
- D. A. M. Barrington, P. Kadau, K. Lange, and P. McKenzie, On the complexity of some probelems on groups input as multiplication tables, Journal of Computer and System Sciences 62:4 (2001), 629-652.
- ...
- D.A.M. Barrington, N. Immerman, and H. Straubing, On uniformity
within NC1, Journal of Computer and System Sciences
41:3 (Dec. 1990) (special issue from IEEE Structures 1988).
- D.A.M. Barrington, H. Straubing, and D. Therien, Non-uniform automata over groups, Information and Computation 89:2 (Dec. 1990),
109-132.
- D.A.M. Barrington, Bounded-width polynomial-size branching programs recognize exactly those languages in NC1,
Journal of Computer and System Sciences 38:1 (1989), 150-164 (special issue from STOC 1986).
- D.A.M. Barrington and D. Therien, Finite Monoids and the fine structure
of NC1, Journal of the ACM 35:4 (Oct. 1988),
941-952.
- D.A. Barrington, Width-3 permutation branching programs, M.I.T. L.C.S. Technical report TM-293 (1985).
Last modified 18 August 2009