dblp.uni-trier.dewww.uni-trier.de

David A. Mix Barrington Vis

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo
Home Page

*2006
46EEEric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy: Grid Graph Reachability Problems. IEEE Conference on Computational Complexity 2006: 299-313
2005
45EEEric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy: Grid Graph Reachability Problems Electronic Colloquium on Computational Complexity (ECCC)(149): (2005)
44EEDavid 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
43EEWilliam 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
42EEEric 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
40EEEric 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
37EEDavid 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
36EEDavid A. Mix Barrington, Pierre McKenzie, Cristopher Moore, Pascal Tesson, Denis Thérien: Equation Satisfiability and Program Satisfiability for Finite Monoids. MFCS 2000: 172-181
35EEEric Allender, David A. Mix Barrington: Uniform Circuits for Division: Consequences and Problems Electronic Colloquium on Computational Complexity (ECCC) 7(65): (2000)
1999
34EEEric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh: Bounded Depth Arithmetic Circuits: Counting and Closure. ICALP 1999: 149-158
33EEDavid A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum: On Monotone Planar Circuits. IEEE Conference on Computational Complexity 1999: 24-
32EEDavid A. Mix Barrington, Howard Straubing: Lower bounds for modular counting by circuits with modular gates. Computational Complexity 8(3): 258-272 (1999)
31EEEric 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
30EEAndris Ambainis, David A. Mix Barrington, Huong LeThanh: On Counting AC0 Circuits with Negative Constants. MFCS 1998: 409-417
29EEDavid 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)
27EEAndris Ambainis, David A. Mix Barrington, Huong LeThanh: On Counting AC0 Circuits with Negative Constants Electronic Colloquium on Computational Complexity (ECCC) 5(20): (1998)
1997
26EEDavid 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
18EEZhi-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
7EEDavid 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
4EEDavid A. Mix Barrington, Denis Thérien: Finite monoids and the fine structure of NC1. J. ACM 35(4): 941-952 (1988)
1987
3EEDavid 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

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

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)