![](https://dblp.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
default search action
David A. Mix Barrington
Person information
- affiliation: University of Massachusetts Amherst, USA
Refine list
![note](https://dblp.uni-trier.de/img/note-mark.dark.12x12.png)
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
Journal Articles
- 2014
- [j21]William Hesse, Eric Allender
, David A. Mix Barrington:
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. 80(2): 496-497 (2014) - 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) - 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) - 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) - 1999
- [j15]David A. Mix Barrington, Howard Straubing:
Lower bounds for modular counting by circuits with modular gates. Comput. Complex. 8(3): 258-272 (1999) - 1998
- [j14]Gábor Tardos
, David A. Mix Barrington:
A Lower Bound on the Mod 6 Degree of the Or Function. Comput. Complex. 7(2): 99-108 (1998) - 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) - 1994
- [j12]David A. Mix Barrington, Howard Straubing:
Complex Polynomials and Circuit Lower Bounds for Modular Counting. Comput. Complex. 4: 325-338 (1994) - [j11]David A. Mix Barrington, Richard Beigel, Steven Rudich:
Representing Boolean Functions as Polynomials Modulo Composite Numbers. Comput. Complex. 4: 367-382 (1994) - [j10]Gudmund Skovbjerg Frandsen, Mark Valence, David A. Mix Barrington:
Some Results on Uniform Arithmetic Circuit Complexity. Math. Syst. Theory 27(2): 105-124 (1994) - 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) - 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) - 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. Math. Syst. 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) - 1988
- [j1]David A. Mix Barrington, Denis Thérien:
Finite monoids and the fine structure of NC1. J. ACM 35(4): 941-952 (1988)
Conference and Workshop Papers
- 2006
- [c22]Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta
, Sambuddha Roy:
Grid Graph Reachability Problems. CCC 2006: 299-313 - 2001
- [c21]Eric Allender, David A. Mix Barrington, William Hesse:
Uniform Circuits for Division: Consequences and Problems. CCC 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 - 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. CCC 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 - 1999
- [c17]David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum:
On Monotone Planar Circuits. CCC 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 - 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 - 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
- [c11]David A. Mix Barrington, Neil Immerman:
Time, Hardware, and Uniformity. SCT 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
- [c9]David A. Mix Barrington:
Quasipolynomial Size Circuit Classes. SCT 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
- [c6]David A. Mix Barrington, Howard Straubing:
Superlinear Lower Bounds for Bounded-Width Branching Programs. SCT 1991: 305-313 - 1989
- [c5]David A. Mix Barrington, Pierre McKenzie:
Oracle Branching Programs and Logspace versus P. MFCS 1989: 370-379 - 1988
- [c4]David A. Mix Barrington, Neil Immerman, Howard Straubing:
On uniformity within NC1. SCT 1988: 47-59 - 1987
- [c3]David A. Mix Barrington, Denis Thérien:
Non-Uniform Automata Over Groups. ICALP 1987: 163-173 - [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
Informal and Other Publications
- 2005
- [i6]Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy:
Grid Graph Reachability Problems. Electron. Colloquium Comput. Complex. TR05 (2005) - 2001
- [i5]Eric Allender, David A. Mix Barrington, William Hesse:
Uniform Circuits for Division: Consequences and Problems. Electron. Colloquium Comput. Complex. TR01 (2001) - 2000
- [i4]Eric Allender, David A. Mix Barrington:
Uniform Circuits for Division: Consequences and Problems. Electron. Colloquium Comput. Complex. TR00 (2000) - 1999
- [i3]Eric Allender, Andris Ambainis, David A. Mix Barrington, Samir Datta, Huong LeThanh:
Bounded Depth Arithmetic Circuits: Counting and Closure. Electron. Colloquium Comput. Complex. TR99 (1999) - 1998
- [i2]Andris Ambainis, David A. Mix Barrington, Huong LeThanh:
On Counting AC0 Circuits with Negative Constants. Electron. Colloquium Comput. Complex. TR98 (1998) - 1997
- [i1]David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, Sven Skyum:
Searching constant width mazes captures the AC0 hierarchy. Electron. Colloquium Comput. Complex. TR97 (1997)
Coauthor Index
![](https://dblp.uni-trier.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-04-24 22:58 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint