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, 45 (2009), 675-723 (special issue from
IEEE 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 problems on groups input as multiplication tables, Journal of Computer and System Sciences 62:4 (2001), 629-652.
- ...
- D. A. M. Barrington, Quasipolynomial size
circuit classes, Structure in Complexity Theory, Seventh
Annual
Conference (1992), 86-93.
- 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 December 2010