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.

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

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.