- CSB - MetaPress - Google - Bing - Yahoo
 | 2009 | |
|---|---|---|
| j20 |      | Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy: Planar and Grid Graph Reachability Problems. Theory Comput. Syst. 45(4): 675-723 (2009) |
| 2006 | ||
| c22 | | 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 | ||
| j19 | | 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) |
| i6 | | Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy: Grid Graph Reachability Problems. Electronic Colloquium on Computational Complexity (ECCC)(149) (2005) |
| 2002 | ||
| j18 | | 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 | ||
| j17 | | 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) |
| j16 | | Neil Immerman, Jonathan F. Buss, David A. Mix Barrington: Number of Variables Is Equivalent to Space. J. Symb. Log. 66(3): 1217-1230 (2001) |
| c21 | | Eric Allender, David A. Mix Barrington, William Hesse: Uniform Circuits for Division: Consequences and Problems. IEEE Conference on Computational Complexity 2001: 150-159 |
| c20 | | David A. Mix Barrington, Neil Immerman, Clemens Lautemann, Nicole Schweikardt, Denis Thérien: The Crane Beach Conjecture. LICS 2001: 187-196 |
| i5 | | Eric Allender, David A. Mix Barrington, William Hesse: Uniform Circuits for Division: Consequences and Problems. Electronic Colloquium on Computational Complexity (ECCC) 8(33) (2001) |
| 2000 | ||
| c19 | | 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 |
| c18 | | 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 |
| i4 | | Eric Allender, David A. Mix Barrington: Uniform Circuits for Division: Consequences and Problems. Electronic Colloquium on Computational Complexity (ECCC) 7(65) (2000) |
| 1999 | ||
| j15 | | David A. Mix Barrington, Howard Straubing: Lower bounds for modular counting by circuits with modular gates. Computational Complexity 8(3): 258-272 (1999) |
| c17 | | David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum: On Monotone Planar Circuits. IEEE Conference on Computational Complexity 1999: 24- |
| c16 | | Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh: Bounded Depth Arithmetic Circuits: Counting and Closure. ICALP 1999: 149-158 |
| i3 | | 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 | ||
| j14 | | 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) |
| c15 | | Andris Ambainis, David A. Mix Barrington, Huong LeThanh: On Counting AC0 Circuits with Negative Constants. MFCS 1998: 409-417 |
| c14 | | David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum: Searching Constant Width Mazes Captures the AC0 Hierarchy. STACS 1998: 73-83 |
| i2 | | 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 | ||
| i1 | | 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 | ||
| j13 | | David A. Mix Barrington, Howard Straubing: Superlinear Lower Bounds for Bounded-Width Branching Programs. J. Comput. Syst. Sci. 50(3): 374-381 (1995) |
| c13 |  | Gábor Tardos, David A. Mix Barrington: A Lower Bound on the Mod 6 Degree of the OR Function. ISTCS 1995: 52-56 |
| c12 | | David A. Mix Barrington, Howard Straubing: Lower Bounds for Modular Counting by Circuits with Modular Gates. LATIN 1995: 60-71 |
| 1994 | ||
| j12 | | David A. Mix Barrington, Howard Straubing: Complex Polynomials and Circuit Lower Bounds for Modular Counting. Computational Complexity 4: 325-338 (1994) |
| j11 | | David A. Mix Barrington, Richard Beigel, Steven Rudich: Representing Boolean Functions as Polynomials Modulo Composite Numbers. Computational Complexity 4: 367-382 (1994) |
| j10 | | Gudmund Skovbjerg Frandsen, Mark Valence, David A. Mix Barrington: Some Results on Uniform Arithmetic Circuit Complexity. Mathematical Systems Theory 27(2): 105-124 (1994) |
| c11 | | David A. Mix Barrington, Neil Immerman: Time, Hardware, and Uniformity. Structure in Complexity Theory Conference 1994: 176-185 |
| 1993 | ||
| c10 | | 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 | ||
| j9 | | 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) |
| c9 | | David A. Mix Barrington: Quasipolynomial Size Circuit Classes. Structure in Complexity Theory Conference 1992: 86-93 |
| c8 | | David A. Mix Barrington, Howard Straubing: Complex Polynomials and Circuit Lower Bounds for Modular Counting. LATIN 1992: 24-31 |
| c7 | | David A. Mix Barrington, Richard Beigel, Steven Rudich: Representing Boolean Functions as Polynomials Modulo Composite Numbers (Extended Abstract). STOC 1992: 455-461 |
| 1991 | ||
| j8 | | David A. Mix Barrington, Pierre McKenzie: Oracle branching programs and Logspace versus P. Inf. Comput. 95(1): 96-115 (1991) |
| j7 | | David A. Mix Barrington, James C. Corbett: A Note on Some Languages in Uniform ACC0. Theor. Comput. Sci. 78(2): 357-362 (1991) |
| c6 | | David A. Mix Barrington, Howard Straubing: Superlinear Lower Bounds for Bounded-Width Branching Programs. Structure in Complexity Theory Conference 1991: 305-313 |
| 1990 | ||
| j6 | | David A. Mix Barrington, Howard Straubing, Denis Thérien: Non-Uniform Automata Over Groups. Inf. Comput. 89(2): 109-132 (1990) |
| j5 | | David A. Mix Barrington, Neil Immerman, Howard Straubing: On Uniformity within NC¹. J. Comput. Syst. Sci. 41(3): 274-306 (1990) |
| j4 | | David A. Mix Barrington: Extensions of an Idea of McNaughton. Mathematical Systems Theory 23(3): 147-164 (1990) |
| 1989 | ||
| j3 | | David A. Mix Barrington, James C. Corbett: On the Relative Complexity of Some Languages in NC. Inf. Process. Lett. 32(5): 251-256 (1989) |
| j2 | | 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) |
| c5 | | David A. Mix Barrington, Pierre McKenzie: Oracle Branching Programs and Logspace versus P. MFCS 1989: 370-379 |
| 1988 | ||
| j1 | | David A. Mix Barrington, Denis Thérien: Finite monoids and the fine structure of NC1. J. ACM 35(4): 941-952 (1988) |
| c4 | | David A. Mix Barrington, Neil Immerman, Howard Straubing: On uniformity within NC1. Structure in Complexity Theory Conference 1988: 47-59 |
| 1987 | ||
| c3 | | |
| c2 | | David A. Mix Barrington, Denis Thérien: Finite Monoids and the Fine Structure of NC¹. STOC 1987: 101-109 |
| 1986 | ||
| c1 | | David A. Mix Barrington: Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹. STOC 1986: 1-5 |
Data released under the ODC-BY 1.0 license — See also our legal information page