Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR11-095 | 12th May 2012 01:42

The lower reaches of circuit uniformity

RSS-Feed




Revision #1
Authors: Christoph Behle, Andreas Krebs, Klaus-Joern Lange, Pierre McKenzie
Accepted on: 12th May 2012 01:42
Downloads: 4197
Keywords: 


Abstract:

The effect of severely tightening the uniformity of Boolean circuit families is investigated. The impact on NC1 and its subclasses is shown to depend on the characterization chosen for the class, while classes such as P appear to be more robust. Tightly uniform subclasses of NC1 whose separation may be within reach of current techniques emerge.



Changes to previous version:

Results are stated in more clear way, and overall readability was improved.


Paper:

TR11-095 | 22nd June 2011 22:55

Low uniform versions of NC1





TR11-095
Authors: Christoph Behle, Andreas Krebs, Klaus-Joern Lange, Pierre McKenzie
Publication: 23rd June 2011 06:21
Downloads: 3267
Keywords: 


Abstract:

In the setting known as DLOGTIME-uniformity,
the fundamental complexity classes
AC^0\subset ACC^0\subseteq TC^0\subseteq NC^1 have several
robust characterizations.
In this paper we refine uniformity further and examine the impact
of these refinements on NC^1 and its subclasses.
When applied to the logarithmic circuit depth characterization of NC^1,
some refinements leave NC^1 unchanged
while others collapse NC^1 to NC^0.
Thus we study refinements of other circuit characterizations of NC^1.
In the case of the AC0(A_5) characterization of NC^1,
where A_5 is the NC^1-complete word problem of the group A_5,
our refinements collapse NC^1 to a subset of the regular languages.
For the AC^0(D^+) characterizations of NC^1,
where D^+ is the NC^1-complete language capturing the formula
value problem, interestingly, these
refinements scale down to circuits with linear fan-in.
In particular, the latter refinements bring to the fore two classes, denoted
FO[<]-uniform AC^0(D^+)_{LIN} and
FO[<]-uniform TC^0_{LIN}, whose separation may be within the
reach of current lower bound techniques, and whose separation would amount
to distinguishing the power of a MAJ gate from that of a D^+ gate.



ISSN 1433-8092 | Imprint