# Circuit uniformities more restrictive than $DLOGTIME$

Definitions:

• The "direct connection language" of a circuit family is the set of tuples $$\langle t, a, b, y \rangle$$, where $$a$$ and $$b$$ are node/gate numbers in the $$n$$th circuit in the family, $$t$$ is the type of gate $$a$$, gate $$b$$ is a child of gate $$a$$, and $$y$$ is a padding string of length $$n$$.
• A circuit family is $$DLOGTIME$$-uniform if its direct connection language can be recognized in $$O(\log(n))$$ time by a deterministic multi-tape Turing machine (with an index tape for random access to the input).

$$DLOGTIME$$-uniformity was introduced by Barrington et al. here, and seems to be the standard lowest uniformity measure used for e.g. constant-depth circuit classes ($$AC^0$$, $$ACC^0$$, etc.). Are there circuit uniformities more strict than $$DLOGTIME$$-uniformity, especially with pre-existing basis in literature? The only one I could find was Rational uniformity from this paper, but it doesn't seem to have caught on. If there are no other measures used in the literature now, I would still accept "theoretical" uniformity measures more strict/sharp/restrictive than $$DLOGTIME$$-uniformity.

• One way to make it stricter is that instead of just recognizing the direct connection language, you require that you can compute the $i$th child of $t$ in time $O(\log n)$. Feb 1, 2022 at 7:07

• @Jake The paper does actually involve some notions of uniformity: you can turn the conclusion of Theorem 5 into a definition. (The theorem states that it is equivalent to logspace unifiormity, but that of course only holds since they are dealing with unrestricted Boolean circuits.) In order to make it stricter than DLOGTIME uniformity, you’d have to require that given $n$ and $u\in\{0,1\}^{O(\log n)}$, you can compute $D(u)$ in time $O(\log n)$ rather than $O(\operatorname{poly}\log n)$. Feb 1, 2022 at 7:18