3
$\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.

Improve this question
$\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$
    – Emil Jeřábek
    Feb 1, 2022 at 7:07

1 Answer 1

Reset to default
3
$\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

Improve this answer
$\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$
    – Emil Jeřábek
    Feb 1, 2022 at 7:18

Your Answer

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

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