David A. Mix Barrington

According to our database, David A. Mix Barrington authored at least 37 papers between 1987 and 2014.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2014

Corrigendum to "Uniform constant-depth threshold circuits for division and iterated multiplication" [J. Comput. System Sci. 65(4) (2002) 695-716].

William Hesse, Eric Allender, David A. Mix Barrington

J. Comput. Syst. Sci., 2014

2009

Planar and Grid Graph Reachability Problems.

Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy

Theory Comput. Syst., 2009

2005

First-order expressibility of languages with neutral letters or: The Crane Beach conjecture.

David A. Mix Barrington, Neil Immerman, Clemens Lautemann, Nicole Schweikardt, Denis Thérien

J. Comput. Syst. Sci., 2005

Grid Graph Reachability Problems

Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy

Electron. Colloquium Comput. Complex., 2005

2002

Uniform constant-depth threshold circuits for division and iterated multiplication.

William Hesse, Eric Allender, David A. Mix Barrington

J. Comput. Syst. Sci., 2002

2001

Number of Variables Is Equivalent to Space.

Neil Immerman, Jonathan F. Buss, David A. Mix Barrington

J. Symb. Log., 2001

On the Complexity of Some Problems on Groups Input as Multiplication Tables.

David A. Mix Barrington, Peter Kadau, Klaus-Jörn Lange, Pierre McKenzie

J. Comput. Syst. Sci., 2001

Uniform Circuits for Division: Consequences and Problems

Eric Allender, David A. Mix Barrington, William Hesse

Electron. Colloquium Comput. Complex., 2001

The Crane Beach Conjecture.

David A. Mix Barrington, Neil Immerman, Clemens Lautemann, Nicole Schweikardt, Denis Thérien

Proceedings of the 16th Annual IEEE Symposium on Logic in Computer Science, 2001

2000

Uniform Circuits for Division: Consequences and Problems

Eric Allender, David A. Mix Barrington

Electron. Colloquium Comput. Complex., 2000

Equation Satisfiability and Program Satisfiability for Finite Monoids.

David A. Mix Barrington, Pierre McKenzie, Cristopher Moore, Pascal Tesson, Denis Thérien

Proceedings of the Mathematical Foundations of Computer Science 2000, 2000

1999

Bounded Depth Arithmetic Circuits: Counting and Closure

Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh

Electron. Colloquium Comput. Complex., 1999

Lower bounds for modular counting by circuits with modular gates.

David A. Mix Barrington, Howard Straubing

Comput. Complex., 1999

On Monotone Planar Circuits.

David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum

Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998

On Counting AC⁰ Circuits with Negative Constants

Andris Ambainis, David A. Mix Barrington, Huong LeThanh

Electron. Colloquium Comput. Complex., 1998

A Lower Bound on the Mod 6 Degree of the Or Function.

Gábor Tardos, David A. Mix Barrington

Comput. Complex., 1998

1997

Searching constant width mazes captures the AC⁰ hierarchy

David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum

Electron. Colloquium Comput. Complex., 1997

1995

Superlinear Lower Bounds for Bounded-Width Branching Programs.

David A. Mix Barrington, Howard Straubing

J. Comput. Syst. Sci., 1995

1994

Some Results on Uniform Arithmetic Circuit Complexity.

Gudmund Skovbjerg Frandsen, Mark Valence, David A. Mix Barrington

Math. Syst. Theory, 1994

Complex Polynomials and Circuit Lower Bounds for Modular Counting.

David A. Mix Barrington, Howard Straubing

Comput. Complex., 1994

Representing Boolean Functions as Polynomials Modulo Composite Numbers.

David A. Mix Barrington, Richard Beigel, Steven Rudich

Comput. Complex., 1994

Time, Hardware, and Uniformity.

David A. Mix Barrington, Neil Immerman

Proceedings of the Ninth Annual Structure in Complexity Theory Conference, Amsterdam, The Netherlands, June 28, 1994

1993

Computing Symmetric Functions with AND/OR Circuits and a Single MAJORITY Gate.

Zhi-Li Zhang, David A. Mix Barrington, Jun Tarui

Proceedings of the STACS 93, 1993

1992

Regular Languages in NC¹.

David A. Mix Barrington, Kevin J. Compton, Howard Straubing, Denis Thérien

J. Comput. Syst. Sci., 1992

Representing Boolean Functions as Polynomials Modulo Composite Numbers (Extended Abstract)

David A. Mix Barrington, Richard Beigel, Steven Rudich

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Quasipolynomial Size Circuit Classes.

David A. Mix Barrington

Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992

1991

Oracle branching programs and Logspace versus P

David A. Mix Barrington, Pierre McKenzie

Inf. Comput., November, 1991

A Note on Some Languages in Uniform ACC0.

David A. Mix Barrington, James C. Corbett

Theor. Comput. Sci., 1991

1990

Non-Uniform Automata Over Groups

David A. Mix Barrington, Howard Straubing, Denis Thérien

Inf. Comput., December, 1990

Extensions of an Idea of McNaughton.

David A. Mix Barrington

Math. Syst. Theory, 1990

On Uniformity within NC¹.

David A. Mix Barrington, Neil Immerman, Howard Straubing

J. Comput. Syst. Sci., 1990

1989

Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹.

David A. Mix Barrington

J. Comput. Syst. Sci., 1989

On the Relative Complexity of Some Languages in NC.

David A. Mix Barrington, James C. Corbett

Inf. Process. Lett., 1989

1988

Finite monoids and the fine structure of NC¹.

David A. Mix Barrington, Denis Thérien

J. ACM, 1988

On uniformity within NC¹.

David A. Mix Barrington, Neil Immerman, Howard Straubing

Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

1987

Finite Monoids and the Fine Structure of NC¹

David A. Mix Barrington, Denis Thérien

Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

Non-Uniform Automata Over Groups.

David A. Mix Barrington, Denis Thérien

Proceedings of the Automata, Languages and Programming, 14th International Colloquium, 1987