David A. Mix Barrington

49 papers A* 6A 6B 5Journal 27Unranked 5

Year	Rank	Type	Title / Venue / Authors
2014	J	`jnl`	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. William Hesse, Eric Allender, David A. Mix Barrington
2009	J	`jnl`	Planar and Grid Graph Reachability Problems. Theory Comput. Syst. Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy
2006	A	`conf`	Grid Graph Reachability Problems. CCC Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy
2005	J	`jnl`	First-order expressibility of languages with neutral letters or: The Crane Beach conjecture. J. Comput. Syst. Sci. David A. Mix Barrington, Neil Immerman, Clemens Lautemann, Nicole Schweikardt, Denis Thérien
2005	J	`jnl`	Grid Graph Reachability Problems Electron. Colloquium Comput. Complex. Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy
2002	J	`jnl`	Uniform constant-depth threshold circuits for division and iterated multiplication. J. Comput. Syst. Sci. William Hesse, Eric Allender, David A. Mix Barrington
2001	J	`jnl`	Number of Variables Is Equivalent to Space. J. Symb. Log. Neil Immerman, Jonathan F. Buss, David A. Mix Barrington
2001	J	`jnl`	On the Complexity of Some Problems on Groups Input as Multiplication Tables. J. Comput. Syst. Sci. David A. Mix Barrington, Peter Kadau, Klaus-Jörn Lange, Pierre McKenzie
2001	A*	`conf`	The Crane Beach Conjecture. LICS David A. Mix Barrington, Neil Immerman, Clemens Lautemann, Nicole Schweikardt, Denis Thérien
2001	J	`jnl`	Uniform Circuits for Division: Consequences and Problems Electron. Colloquium Comput. Complex. Eric Allender, David A. Mix Barrington, William Hesse
2001	A	`conf`	Uniform Circuits for Division: Consequences and Problems. CCC Eric Allender, David A. Mix Barrington, William Hesse
2000	B	`conf`	Equation Satisfiability and Program Satisfiability for Finite Monoids. MFCS David A. Mix Barrington, Pierre McKenzie, Cristopher Moore, Pascal Tesson, Denis Thérien
2000	A	`conf`	On the Complexity of Some Problems on Groups Input as Multiplication Tables. CCC David A. Mix Barrington, Peter Kadau, Klaus-Jörn Lange, Pierre McKenzie
2000	J	`jnl`	Uniform Circuits for Division: Consequences and Problems Electron. Colloquium Comput. Complex. Eric Allender, David A. Mix Barrington
1999	J	`jnl`	Bounded Depth Arithmetic Circuits: Counting and Closure Electron. Colloquium Comput. Complex. Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh
1999	A*	`conf`	Bounded Depth Arithmetic Circuits: Counting and Closure. ICALP Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh
1999	J	`jnl`	Lower bounds for modular counting by circuits with modular gates. Comput. Complex. David A. Mix Barrington, Howard Straubing
1999	A	`conf`	On Monotone Planar Circuits. CCC David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum
1998	J	`jnl`	A Lower Bound on the Mod 6 Degree of the Or Function. Comput. Complex. Gábor Tardos, David A. Mix Barrington
1998	B	`conf`	On Counting AC MFCS Andris Ambainis, David A. Mix Barrington, Huong LeThanh
1998	J	`jnl`	On Counting AC Electron. Colloquium Comput. Complex. Andris Ambainis, David A. Mix Barrington, Huong LeThanh
1998	A	`conf`	Searching Constant Width Mazes Captures the AC STACS David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum
1997	J	`jnl`	Searching constant width mazes captures the AC Electron. Colloquium Comput. Complex. David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum
1995	—	`conf`	A Lower Bound on the Mod 6 Degree of the OR Function. ISTCS Gábor Tardos, David A. Mix Barrington
1995	B	`conf`	Lower Bounds for Modular Counting by Circuits with Modular Gates. LATIN David A. Mix Barrington, Howard Straubing
1995	J	`jnl`	Superlinear Lower Bounds for Bounded-Width Branching Programs. J. Comput. Syst. Sci. David A. Mix Barrington, Howard Straubing
1994	J	`jnl`	Complex Polynomials and Circuit Lower Bounds for Modular Counting. Comput. Complex. David A. Mix Barrington, Howard Straubing
1994	J	`jnl`	Representing Boolean Functions as Polynomials Modulo Composite Numbers. Comput. Complex. David A. Mix Barrington, Richard Beigel, Steven Rudich
1994	J	`jnl`	Some Results on Uniform Arithmetic Circuit Complexity. Math. Syst. Theory Gudmund Skovbjerg Frandsen, Mark Valence, David A. Mix Barrington
1994	—	`conf`	Time, Hardware, and Uniformity. SCT David A. Mix Barrington, Neil Immerman
1993	A	`conf`	Computing Symmetric Functions with AND/OR Circuits and a Single MAJORITY Gate. STACS Zhi-Li Zhang, David A. Mix Barrington, Jun Tarui
1992	B	`conf`	Complex Polynomials and Circuit Lower Bounds for Modular Counting. LATIN David A. Mix Barrington, Howard Straubing
1992	—	`conf`	Quasipolynomial Size Circuit Classes. SCT David A. Mix Barrington
1992	J	`jnl`	Regular Languages in NC¹. J. Comput. Syst. Sci. David A. Mix Barrington, Kevin J. Compton, Howard Straubing, Denis Thérien
1992	A*	`conf`	Representing Boolean Functions as Polynomials Modulo Composite Numbers (Extended Abstract) STOC David A. Mix Barrington, Richard Beigel, Steven Rudich
1991	J	`jnl`	A Note on Some Languages in Uniform ACC0. Theor. Comput. Sci. David A. Mix Barrington, James C. Corbett
1991	J	`jnl`	Oracle branching programs and Logspace versus P Inf. Comput. David A. Mix Barrington, Pierre McKenzie
1991	—	`conf`	Superlinear Lower Bounds for Bounded-Width Branching Programs. SCT David A. Mix Barrington, Howard Straubing
1990	J	`jnl`	Extensions of an Idea of McNaughton. Math. Syst. Theory David A. Mix Barrington
1990	J	`jnl`	Non-Uniform Automata Over Groups Inf. Comput. David A. Mix Barrington, Howard Straubing, Denis Thérien
1990	J	`jnl`	On Uniformity within NC¹. J. Comput. Syst. Sci. David A. Mix Barrington, Neil Immerman, Howard Straubing
1989	J	`jnl`	Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹. J. Comput. Syst. Sci. David A. Mix Barrington
1989	J	`jnl`	On the Relative Complexity of Some Languages in NC. Inf. Process. Lett. David A. Mix Barrington, James C. Corbett
1989	B	`conf`	Oracle Branching Programs and Logspace versus P. MFCS David A. Mix Barrington, Pierre McKenzie
1988	J	`jnl`	Finite monoids and the fine structure of NC J. ACM David A. Mix Barrington, Denis Thérien
1988	—	`conf`	On uniformity within NC SCT David A. Mix Barrington, Neil Immerman, Howard Straubing
1987	A*	`conf`	Finite Monoids and the Fine Structure of NC¹ STOC David A. Mix Barrington, Denis Thérien
1987	A*	`conf`	Non-Uniform Automata Over Groups. ICALP David A. Mix Barrington, Denis Thérien
1986	A*	`conf`	Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹ STOC David A. Mix Barrington