3
$\begingroup$

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

$\endgroup$
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 at 1:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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