David A. Mix Barrington

Affiliations:
  • University of Massachusetts Amherst, USA


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

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

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

2009
Planar and Grid Graph Reachability Problems.
Theory Comput. Syst., 2009

2005
First-order expressibility of languages with neutral letters or: The Crane Beach conjecture.
J. Comput. Syst. Sci., 2005

Grid Graph Reachability Problems
Electron. Colloquium Comput. Complex., 2005

2002
Uniform constant-depth threshold circuits for division and iterated multiplication.
J. Comput. Syst. Sci., 2002

2001
Number of Variables Is Equivalent to Space.
J. Symb. Log., 2001

On the Complexity of Some Problems on Groups Input as Multiplication Tables.
J. Comput. Syst. Sci., 2001

Uniform Circuits for Division: Consequences and Problems
Electron. Colloquium Comput. Complex., 2001

The Crane Beach Conjecture.
Proceedings of the 16th Annual IEEE Symposium on Logic in Computer Science, 2001

2000
Uniform Circuits for Division: Consequences and Problems
Electron. Colloquium Comput. Complex., 2000

Equation Satisfiability and Program Satisfiability for Finite Monoids.
Proceedings of the Mathematical Foundations of Computer Science 2000, 2000

1999
Bounded Depth Arithmetic Circuits: Counting and Closure
Electron. Colloquium Comput. Complex., 1999

Lower bounds for modular counting by circuits with modular gates.
Comput. Complex., 1999

On Monotone Planar Circuits.
Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998
On Counting AC<sup>0</sup> Circuits with Negative Constants
Electron. Colloquium Comput. Complex., 1998

A Lower Bound on the Mod 6 Degree of the Or Function.
Comput. Complex., 1998

1997
Searching constant width mazes captures the AC<sup>0</sup> hierarchy
Electron. Colloquium Comput. Complex., 1997

1995
Superlinear Lower Bounds for Bounded-Width Branching Programs.
J. Comput. Syst. Sci., 1995

1994
Some Results on Uniform Arithmetic Circuit Complexity.
Math. Syst. Theory, 1994

Complex Polynomials and Circuit Lower Bounds for Modular Counting.
Comput. Complex., 1994

Representing Boolean Functions as Polynomials Modulo Composite Numbers.
Comput. Complex., 1994

Time, Hardware, and Uniformity.
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.
Proceedings of the STACS 93, 1993

1992
Regular Languages in NC¹.
J. Comput. Syst. Sci., 1992

Representing Boolean Functions as Polynomials Modulo Composite Numbers (Extended Abstract)
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Quasipolynomial Size Circuit Classes.
Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992

1991
Oracle branching programs and Logspace versus P
Inf. Comput., November, 1991

A Note on Some Languages in Uniform ACC0.
Theor. Comput. Sci., 1991

1990
Non-Uniform Automata Over Groups
Inf. Comput., December, 1990

Extensions of an Idea of McNaughton.
Math. Syst. Theory, 1990

On Uniformity within NC¹.
J. Comput. Syst. Sci., 1990

1989
Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹.
J. Comput. Syst. Sci., 1989

On the Relative Complexity of Some Languages in NC.
Inf. Process. Lett., 1989

1988
Finite monoids and the fine structure of NC<sup>1</sup>.
J. ACM, 1988

On uniformity within NC<sup>1</sup>.
Proceedings of the Proceedings: Third Annual Structure in Complexity Theory Conference, 1988

1987
Finite Monoids and the Fine Structure of NC¹
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

Non-Uniform Automata Over Groups.
Proceedings of the Automata, Languages and Programming, 14th International Colloquium, 1987


  Loading...