Fakultät für Informatik
-
Technische Universität München
Lehrstuhl für Effiziente Algorithmen
Die bibliographische Datenbank LEABib
Suchen
•
Liste der Journale
•
Liste der Serien
•
Liste der Konferenzen
•
Ausgewählte Publikationen
Hilfe
Suche: Author="Barrington, David A. Mix"
Als [
bib
] [
pdf
] [
ps
] [
dvi
] [
xml
] herunterladen.
Corrigendum to ``Uniform constant-depth threshold circuits for division and iterated multiplication''
William Hesse
,
Eric Allender
,
David A. Mix Barrington
Journal of Computer and System Sciences
80
(2), 2014, pp. 496-497
Planar and grid graph reachability problems
Eric Allender
,
David A. Mix Barrington
,
Tanmoy Chakraborty
,
Samir Datta
,
Sambuddha Roy
Theory of Computing Systems
45
(4), 2009, pp. 675-723
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
Journal of Computer and System Sciences
70
(2), 2005, pp. 101-127
Uniform constant-depth threshold circuits for division and iterated multiplication
William Hesse
,
Eric Allender
,
David A. Mix Barrington
Journal of Computer and System Sciences
65
(4), 2002, pp. 695-716
Uniform circuits for division: Consequences and problems
Eric Allender
,
David A. Mix Barrington
,
William Hesse
Technical Report (TR01-033), 2001
Uniform circuits for divison: Consequences and problems
Eric Allender
,
David A. Mix Barrington
,
William Hesse
Proceedings of the 16th Annual IEEE Conference on Computational Complexity (Chicago, Illinois, June 18-21, 2001)
, 2000, pp. 150-159
Bounded depth arithmetic circuits: Counting and closure
Eric Allender
,
Andris Ambainis
,
David A. Mix Barrington
,
Samir Datta
,
Huong LéThanh
Technical Report (TR99-012), 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 (Atlanta, Georgia, May 4-6, 1999)
, 1999, pp. 24-31
Searching constant width mazes captures the
AC^0
hierarchy
David A. Mix Barrington
,
Chi-Jen Lu
,
Peter Bro Miltersen
,
Sven Skyum
Lecture Notes in Computer Science
1373
, 1998, pp. 73-83
Superlinear lower bounds for bounded-width branching programs
David A. Mix Barrington
,
Howard Straubing
Journal of Computer and System Sciences
50
(3), 1995, pp. 374-381
Some results on uniform arithmetic circuit complexity
Gudmund S. Frandsen
,
Mark Valence
,
David A. Mix Barrington
Math. Systems Theory
27
(2), 1994, pp. 105-124
Computing symmetric functions with AND/OR circuits and a single MAJORITY gate
Zhi-Li Zhang
,
David A. Mix Barrington
,
Jun Tarui
Lecture Notes in Computer Science
665
, 1993, pp. 535-544
Representing Boolean functions as polynomials modulo composite numbers
David A. Mix Barrington
,
Richard Beigel
,
Steven Rudich
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, STOC'92 (Victoria, British Columbia, Canada, May 4-6, 1992)
, 1992, pp. 455-461
Regular languages in
NC^1
David A. Mix Barrington
,
Kevin Compton
,
Howard Straubing
,
Denis Thérien
Journal of Computer and System Sciences
44
, 1992, pp. 478-499
Complex polynomials and circuit lower bounds for modular counting
David A. Mix Barrington
,
Howard Straubing
Lecture Notes in Computer Science
583
, 1992, pp. 24-31
Some problems involving Razborov-Smolensky polynomials
David A. Mix Barrington
Boolean function complexity
London Mathematical Society Lecture Note Series 169
, 1992, pp. 109-128
Quasipolynomial size circuit classes
David A. Mix Barrington
Proceedings of the 7th Annual Conference on Structure in Complexity Theory, CSCT'92 (Boston University, Boston, Massachusetts, June 22-25, 1992)
, 1992, pp. 86-93
Oracle branching programs and Logspace versus
\P
David A. Mix Barrington
,
Pierre McKenzie
Information and Computation
95
(1), 1991, November, pp. 96-115
Superlinear lower bounds for bounded-width branching programs
David A. Mix Barrington
,
Howard Straubing
Proceedings of the 6th Annual Conference on Structure in Complexity Theory, CSCT'91 (Chicago, Illinois, June 30-July 3, 1991)
, 1991, pp. 305-313
A note on some languages in uniform
\mbox{ACC}^0
David A. Mix Barrington
,
James Corbett
Theoretical Computer Science
78
, 1990, pp. 357-362
On uniformity within
NC^1
David A. Mix Barrington
,
Neil Immerman
Journal of Computer and System Sciences
41
, 1990, pp. 274-306
Non-uniform automata over groups
David A. Mix Barrington
,
Howard Straubing
,
Denis Thérien
Information and Computation
89
(2), 1990, December, pp. 109-132
Extensions of an idea of McNaughton
David A. Mix Barrington
Math. Systems Theory
23
, 1990, pp. 147-164
On the relative complexity of some languages in
NC^1
David A. Mix Barrington
,
James Corbett
Information Processing Letters
32
, 1989, pp. 251-256
Finite monoids and the fine structure of
NC^1
David A. Mix Barrington
,
Denis Thérien
Journal of the ACM
35
(4), 1988, pp. 941-952
Seiten 1
2
>