5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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)$. $\endgroup$ Feb 1, 2022 at 7:07

2 Answers 2

5
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jake
    Jan 20, 2022 at 1:17
  • 1
    $\begingroup$ @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)$. $\endgroup$ Feb 1, 2022 at 7:18
4
$\begingroup$

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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.