David A. Mix Barrington

2006
46	EE	Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy: Grid Graph Reachability Problems. IEEE Conference on Computational Complexity 2006: 299-313
2005
45	EE	Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy: Grid Graph Reachability Problems Electronic Colloquium on Computational Complexity (ECCC)(149): (2005)
44	EE	David A. Mix Barrington, Neil Immerman, Clemens Lautemann, Nicole Schweikardt, Denis Thérien: First-order expressibility of languages with neutral letters or: The Crane Beach conjecture. J. Comput. Syst. Sci. 70(2): 101-127 (2005)
2002
43	EE	William Hesse, Eric Allender, David A. Mix Barrington: Uniform constant-depth threshold circuits for division and iterated multiplication. J. Comput. Syst. Sci. 65(4): 695-716 (2002)
2001
42	EE	Eric Allender, David A. Mix Barrington, William Hesse: Uniform Circuits for Division: Consequences and Problems. IEEE Conference on Computational Complexity 2001: 150-159
41		David A. Mix Barrington, Neil Immerman, Clemens Lautemann, Nicole Schweikardt, Denis Thérien: The Crane Beach Conjecture. LICS 2001: 187-196
40	EE	Eric Allender, David A. Mix Barrington, William Hesse: Uniform Circuits for Division: Consequences and Problems Electronic Colloquium on Computational Complexity (ECCC) 8(33): (2001)
39		David A. Mix Barrington, Peter Kadau, Klaus-Jörn Lange, Pierre McKenzie: On the Complexity of Some Problems on Groups Input as Multiplication Tables. J. Comput. Syst. Sci. 63(2): 186-200 (2001)
38		Neil Immerman, Jonathan F. Buss, David A. Mix Barrington: Number of Variables Is Equivalent to Space. J. Symb. Log. 66(3): 1217-1230 (2001)
2000
37	EE	David A. Mix Barrington, Peter Kadau, Klaus-Jörn Lange, Pierre McKenzie: On the Complexity of Some Problems on Groups Input as Multiplication Tables. IEEE Conference on Computational Complexity 2000: 62-69
36	EE	David A. Mix Barrington, Pierre McKenzie, Cristopher Moore, Pascal Tesson, Denis Thérien: Equation Satisfiability and Program Satisfiability for Finite Monoids. MFCS 2000: 172-181
35	EE	Eric Allender, David A. Mix Barrington: Uniform Circuits for Division: Consequences and Problems Electronic Colloquium on Computational Complexity (ECCC) 7(65): (2000)
1999
34	EE	Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh: Bounded Depth Arithmetic Circuits: Counting and Closure. ICALP 1999: 149-158
33	EE	David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum: On Monotone Planar Circuits. IEEE Conference on Computational Complexity 1999: 24-
32	EE	David A. Mix Barrington, Howard Straubing: Lower bounds for modular counting by circuits with modular gates. Computational Complexity 8(3): 258-272 (1999)
31	EE	Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh: Bounded Depth Arithmetic Circuits: Counting and Closure Electronic Colloquium on Computational Complexity (ECCC) 6(12): (1999)
1998
30	EE	Andris Ambainis, David A. Mix Barrington, Huong LeThanh: On Counting AC0 Circuits with Negative Constants. MFCS 1998: 409-417
29		David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum: Searching Constant Width Mazes Captures the AC0 Hierarchy. STACS 1998: 73-83
28		Gábor Tardos, David A. Mix Barrington: A Lower Bound on the Mod 6 Degree of the Or Function. Computational Complexity 7(2): 99-108 (1998)
27	EE	Andris Ambainis, David A. Mix Barrington, Huong LeThanh: On Counting AC0 Circuits with Negative Constants Electronic Colloquium on Computational Complexity (ECCC) 5(20): (1998)
1997
26	EE	David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum: Searching constant width mazes captures the AC0 hierarchy Electronic Colloquium on Computational Complexity (ECCC) 4(44): (1997)
1995
25		Gábor Tardos, David A. Mix Barrington: A Lower Bound on the Mod 6 Degree of the OR Function. ISTCS 1995: 52-56
24		David A. Mix Barrington, Howard Straubing: Lower Bounds for Modular Counting by Circuits with Modular Gates. LATIN 1995: 60-71
23		David A. Mix Barrington, Howard Straubing: Superlinear Lower Bounds for Bounded-Width Branching Programs. J. Comput. Syst. Sci. 50(3): 374-381 (1995)
1994
22		David A. Mix Barrington, Neil Immerman: Time, Hardware, and Uniformity. Structure in Complexity Theory Conference 1994: 176-185
21		David A. Mix Barrington, Howard Straubing: Complex Polynomials and Circuit Lower Bounds for Modular Counting. Computational Complexity 4: 325-338 (1994)
20		David A. Mix Barrington, Richard Beigel, Steven Rudich: Representing Boolean Functions as Polynomials Modulo Composite Numbers. Computational Complexity 4: 367-382 (1994)
19		Gudmund Skovbjerg Frandsen, Mark Valence, David A. Mix Barrington: Some Results on Uniform Arithmetic Circuit Complexity. Mathematical Systems Theory 27(2): 105-124 (1994)
1993
18		Zhi-Li Zhang, David A. Mix Barrington, Jun Tarui: Computing Symmetric Functions with AND/OR Circuits and a Single MAJORITY Gate. STACS 1993: 535-544
1992
17		David A. Mix Barrington, Howard Straubing: Complex Polynomials and Circuit Lower Bounds for Modular Counting. LATIN 1992: 24-31
16		David A. Mix Barrington, Richard Beigel, Steven Rudich: Representing Boolean Functions as Polynomials Modulo Composite Numbers (Extended Abstract) STOC 1992: 455-461
15		David A. Mix Barrington: Quasipolynomial Size Circuit Classes. Structure in Complexity Theory Conference 1992: 86-93
14		David A. Mix Barrington, Kevin J. Compton, Howard Straubing, Denis Thérien: Regular Languages in NC¹. J. Comput. Syst. Sci. 44(3): 478-499 (1992)
1991
13		David A. Mix Barrington, Howard Straubing: Superlinear Lower Bounds for Bounded-Width Branching Programs. Structure in Complexity Theory Conference 1991: 305-313
12		David A. Mix Barrington, Pierre McKenzie: Oracle branching programs and Logspace versus P Inf. Comput. 95(1): 96-115 (1991)
11		David A. Mix Barrington, James C. Corbett: A Note on Some Languages in Uniform ACC0. Theor. Comput. Sci. 78(2): 357-362 (1991)
1990
10		David A. Mix Barrington, Howard Straubing, Denis Thérien: Non-Uniform Automata Over Groups Inf. Comput. 89(2): 109-132 (1990)
9		David A. Mix Barrington, Neil Immerman, Howard Straubing: On Uniformity within NC¹. J. Comput. Syst. Sci. 41(3): 274-306 (1990)
8		David A. Mix Barrington: Extensions of an Idea of McNaughton. Mathematical Systems Theory 23(3): 147-164 (1990)
1989
7		David A. Mix Barrington, Pierre McKenzie: Oracle Branching Programs and Logspace versus P. MFCS 1989: 370-379
6		David A. Mix Barrington, James C. Corbett: On the Relative Complexity of Some Languages in NC. Inf. Process. Lett. 32(5): 251-256 (1989)
5		David A. Mix Barrington: Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹. J. Comput. Syst. Sci. 38(1): 150-164 (1989)
1988
4	EE	David A. Mix Barrington, Denis Thérien: Finite monoids and the fine structure of NC1. J. ACM 35(4): 941-952 (1988)
1987
3		David A. Mix Barrington, Denis Thérien: Non-Uniform Automata Over Groups. ICALP 1987: 163-173
2		David A. Mix Barrington, Denis Thérien: Finite Monoids and the Fine Structure of NC¹ STOC 1987: 101-109
1986
1		David A. Mix Barrington: Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹ STOC 1986: 1-5

Coauthor Index

1	Eric Allender	[31] [34] [35] [40] [42] [43] [45] [46]
2	Andris Ambainis	[27] [30] [31] [34]
3	Richard Beigel	[16] [20]
4	Jonathan F. Buss	[38]
5	Tanmoy Chakraborty	[45] [46]
6	Kevin J. Compton	[14]
7	James C. Corbett	[6] [11]
8	Samir Datta	[31] [34] [45] [46]
9	Gudmund Skovbjerg Frandsen	[19]
10	William Hesse	[40] [42] [43]
11	Neil Immerman	[9] [22] [38] [41] [44]
12	Peter Kadau	[37] [39]
13	Klaus-Jörn Lange	[37] [39]
14	Clemens Lautemann	[41] [44]
15	Huong LeThanh	[27] [30] [31] [34]
16	Chi-Jen Lu	[26] [29] [33]
17	Pierre McKenzie	[7] [12] [36] [37] [39]
18	Peter Bro Miltersen	[26] [29] [33]
19	Cristopher Moore	[36]
20	Sambuddha Roy	[45] [46]
21	Steven Rudich	[16] [20]
22	Nicole Schweikardt	[41] [44]
23	Sven Skyum	[26] [29] [33]
24	Howard Straubing	[9] [10] [13] [14] [17] [21] [23] [24] [32]
25	Gábor Tardos	[25] [28]
26	Jun Tarui	[18]
27	Pascal Tesson	[36]
28	Denis Thérien	[2] [3] [4] [10] [14] [36] [41] [44]
29	Mark Valence	[19]
30	Zhi-Li Zhang	[18]

Colors in the list of coauthors