<p>DLOGTIME-uniformity is actually <em>not</em> the most commonly used uniformity notion, when defining Uniform <span class="math-container">$NC^1$</span>.  Typically, one would like &quot;Uniform <span class="math-container">$NC^1$</span>&quot; to coincide with the class of problems solvable on an Alternating Turing Machine in time <span class="math-container">$O(\log n)$</span>.  In order to get this equality to go through, it (currently -- and for about the past 40 years) seems to require a more restrictive form of uniformity, where an &quot;extended connection language&quot; is used.  Briefly, this is just like the Direct Connection Language, except that one also needs to be able to tell, given gates <span class="math-container">$g$</span> and <span class="math-container">$h$</span> and a &quot;path&quot; <span class="math-container">$p$</span> of length <span class="math-container">$O(\log n)$</span>, if <span class="math-container">$h$</span> is the gate that is reached from <span class="math-container">$g$</span> by following path <span class="math-container">$p$</span>.  You can find this discussed in the textbook by Heribert Vollmer.</p>
<p>Also, I want to direct you to these papers, which discuss a different approach to defining more restrictive notions of uniformity:</p>
<ul>
<li>Christoph Behle, Klaus-Jörn Lange: FO[&lt;]-Uniformity. CCC 2006: 183-189</li>
<li>Christoph Behle, Andreas Krebs, Klaus-Jörn Lange, Pierre McKenzie: The Lower Reaches of Circuit Uniformity. MFCS 2012: 590-602</li>
</ul>

CC BY-SA 4.0
2023-10-01T00:42:53.817Z
2023-10-01T00:42:53.817Z
Eric Allender
<p>One notion that seems stricter in principle is that of &quot;O(1)-local reductions&quot;, in that each output bit of the reduction only depends on O(1) bits of the input (as well as using logtime uniformity, I believe). See for example <a href="https://www.ccs.neu.edu/home/viola/papers/explicit.pdf" rel="noreferrer">https://www.ccs.neu.edu/home/viola/papers/explicit.pdf</a></p>

CC BY-SA 4.0
2022-01-20T01:17:43.867Z
Thanks for the answer; however, I'm not sure how to use a reduction as a uniformity measure, or else I'm not sure I understand your answer.
Jake
CC BY-SA 4.0
2022-02-01T07:18:51.950Z
@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)$.
Emil Jeřábek
CC BY-SA 4.0
2022-01-18T19:04:45.747Z
2022-01-18T19:04:45.747Z
Ryan Williams
<p>Definitions:</p>
<ul>
<li>The &quot;direct connection language&quot; of a circuit family is the set of tuples <span class="math-container">$\langle t, a, b, y \rangle$</span>, where <span class="math-container">$a$</span> and <span class="math-container">$b$</span> are node/gate numbers in the <span class="math-container">$n$</span>th circuit in the family, <span class="math-container">$t$</span> is the type of gate <span class="math-container">$a$</span>, gate <span class="math-container">$b$</span> is a child of gate <span class="math-container">$a$</span>, and <span class="math-container">$y$</span> is a padding string of length <span class="math-container">$n$</span>.</li>
<li>A circuit family is <span class="math-container">$DLOGTIME$</span>-uniform if its direct connection language can be recognized in <span class="math-container">$O(\log(n))$</span> time by a deterministic multi-tape Turing machine (with an index tape for random access to the input).</li>
</ul>
<p><span class="math-container">$DLOGTIME$</span>-uniformity was introduced by Barrington et al. <a href="https://people.cs.umass.edu/%7Eimmerman/pub/bis.pdf" rel="nofollow noreferrer">here</a>, and seems to be the standard lowest uniformity measure used for e.g. constant-depth circuit classes (<span class="math-container">$AC^0$</span>, <span class="math-container">$ACC^0$</span>, etc.). Are there circuit uniformities more strict than <span class="math-container">$DLOGTIME$</span>-uniformity, especially with pre-existing basis in literature? The only one I could find was Rational uniformity from <a href="https://hal.archives-ouvertes.fr/hal-00701420/document" rel="nofollow noreferrer">this</a> 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 &quot;theoretical&quot; uniformity measures more strict/sharp/restrictive than <span class="math-container">$DLOGTIME$</span>-uniformity.</p>

CC BY-SA 4.0
2022-02-01T07:07:07.627Z
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)$.
Emil Jeřábek
<circuit-complexity><uniformity>
Circuit uniformities more restrictive than $DLOGTIME$
Jake
# Circuit uniformities more restrictive than $DLOGTIME$

(Asked by: username_0 on 2022-01-13)

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](https://people.cs.umass.edu/%7Eimmerman/pub/bis.pdf), 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](https://hal.archives-ouvertes.fr/hal-00701420/document) 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.

**Tags:** circuit-complexity, uniformity
> **Comments:**
> **username_1**: 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)$.  

---

## 2 answers

### Answer by username_3 on 2022-01-18. Score: 5

One notion that seems stricter in principle is that of "O(1)-local reductions", in that each output bit of the reduction only depends on O(1) bits of the input (as well as using logtime uniformity, I believe). See for example <https://www.ccs.neu.edu/home/viola/papers/explicit.pdf>

> **Comments:**
> **username_0**: Thanks for the answer; however, I'm not sure how to use a reduction as a uniformity measure, or else I'm not sure I understand your answer.  
> **username_1**: @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)$.  

---

### Answer by username_2 on 2023-10-01. Score: 4

DLOGTIME-uniformity is actually *not* the most commonly used uniformity notion, when defining Uniform $NC^1$. Typically, one would like "Uniform $NC^1$" to coincide with the class of problems solvable on an Alternating Turing Machine in time $O(\log n)$. In order to get this equality to go through, it (currently -- and for about the past 40 years) seems to require a more restrictive form of uniformity, where an "extended connection language" is used. Briefly, this is just like the Direct Connection Language, except that one also needs to be able to tell, given gates $g$ and $h$ and a "path" $p$ of length $O(\log n)$, if $h$ is the gate that is reached from $g$ by following path $p$. You can find this discussed in the textbook by Heribert Vollmer.

Also, I want to direct you to these papers, which discuss a different approach to defining more restrictive notions of uniformity:

* Christoph Behle, Klaus-Jörn Lange: FO[<]-Uniformity. CCC 2006: 183-189
* Christoph Behle, Andreas Krebs, Klaus-Jörn Lange, Pierre McKenzie: The Lower Reaches of Circuit Uniformity. MFCS 2012: 590-602


---

