5
votes
Circuit uniformities more restrictive than $DLOGTIME$
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 ...
- 27.7k
5
votes
Accepted
Proof of $DLOGTIME-CC^0 = MOD[<,bit]$
I have reached out to the authors of papers [1] and [2], and it seems that the claims were both in error, leaving this an open question.
- 1,234
4
votes
Circuit uniformities more restrictive than $DLOGTIME$
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 ...
- 2,356
1
vote
Accepted
Variable wire weights in DLOGTIME-uniform circuits
After re-reading Barrington et al., it seems that the case of $CC^0$ can be handled by using "group quantifiers", which allow for quantifiers to act over finite groups (i.e. $\mathbb{Z}/m\...
- 1,234
Only top scored, non community-wiki answers of a minimum length are eligible