<p>Maybe an answer to <a href="https://cstheory.stackexchange.com/questions/50972/">this</a></p>
<p>Here input of length and position is binary rather than unary, so traditional &quot;DLOGTIME-uniform&quot; is now &quot;O(n)-uniform&quot;. (If traditional &quot;DLOGTIME-uniform&quot; already take binary input then this question has false assumption)</p>
<p>Surely O(n) isn't that low, so will a lower model lead to weaker result? E.g. is uniformNC∩O(n)-uniform AC0 weaker than uniform AC0?</p>

CC BY-SA 4.0
2022-12-29T18:46:16.353Z
What exactly is your question?
Emil Jeřábek
CC BY-SA 4.0
2022-12-30T01:58:27.253Z
@EmilJeřábek will a lower model(e.g. uniformNC-uniform) lead to weaker result?
l4m2
CC BY-SA 4.0
2022-12-30T08:28:30.910Z
What "result"??
Emil Jeřábek
CC BY-SA 4.0
2022-12-30T08:33:53.320Z
Also, if you consider the input as indices written in binary, then DLOGTIME-uniformity becomes linear-time uniformity rather than polynomial-time uniformity. It *is* actually already defined that way; it is only called DLOGTIME-uniform in reference to the input size of the circuit being uniformized.
Emil Jeřábek
CC BY-SA 4.0
2022-12-30T09:33:50.953Z
@EmilJeřábek The ability it constructs circuit
l4m2
CC BY-SA 4.0
2022-12-30T15:48:25.243Z
So you are simply asking whether it defines the same classes of languages as DLOGTIME uniformity? This likely depends on the circuit class. There is no reason it should be the same in general. Note also that NC^1 is not included in linear time, hence a priori the classes defined by these two uniformities may not even be included in each other. But for the specific question about AC^0, the answer is positive. On the one hand, NC^1 (and even L) is included in LinH by Nepomnjascij's theorem, and LinH-uniform AC^0 in your sense (which is commonly called FO-uniform) equals the usual uniform AC^0...
Emil Jeřábek
CC BY-SA 4.0
2022-12-30T16:02:18.220Z
... On the other hand, uniform AC^0 equals alternating logarithmic time with $O(1)$ alternations; the usual simulation of this machine model by constant-depth circuits makes nodes of the circuit be indexed by configurations of the logtime ATM, with edges corresponding to one configuration yielding another in one step. This can be checked not just in linear time, but even in coNLOGTIME (which is included in uniform AC^0). Thus, for any class $C$ between coNLOGTIME and LinH, $C$-uniform AC^0 in your sense equals the usual DLOGTIME-uniform AC^0. I'd expect the same to hold for any of the usual...
Emil Jeřábek
CC BY-SA 4.0
2022-12-30T16:04:35.027Z
... circuit classes that share the closure properties of AC^0, thus any potential counterexamples should be somewhat unnatural.
Emil Jeřábek
CC BY-SA 4.0
2022-12-30T17:29:55.607Z
@EmilJeřábek then what about weaker e.g. DLOGTIME-uniform? NC0-uniform looks too hard it requires too complete linking
l4m2
<circuit-complexity><uniformity>
Do uniformity lower than DLOGTIME rlead to same result?
l4m2
# Do uniformity lower than DLOGTIME rlead to same result?

(Asked by: username_0 on 2022-12-29)

Maybe an answer to [this](https://cstheory.stackexchange.com/questions/50972/)

Here input of length and position is binary rather than unary, so traditional "DLOGTIME-uniform" is now "O(n)-uniform". (If traditional "DLOGTIME-uniform" already take binary input then this question has false assumption)

Surely O(n) isn't that low, so will a lower model lead to weaker result? E.g. is uniformNC∩O(n)-uniform AC0 weaker than uniform AC0?

**Tags:** circuit-complexity, uniformity
> **Comments:**
> **username_1**: What exactly is your question?  
> **username_0**: @EmilJeřábek will a lower model(e.g. uniformNC-uniform) lead to weaker result?  
> **username_1**: What "result"??  
> **username_1**: Also, if you consider the input as indices written in binary, then DLOGTIME-uniformity becomes linear-time uniformity rather than polynomial-time uniformity. It *is* actually already defined that way; it is only called DLOGTIME-uniform in reference to the input size of the circuit being uniformized.  
> **username_0**: @EmilJeřábek The ability it constructs circuit  
> **username_1**: So you are simply asking whether it defines the same classes of languages as DLOGTIME uniformity? This likely depends on the circuit class. There is no reason it should be the same in general. Note also that NC^1 is not included in linear time, hence a priori the classes defined by these two uniformities may not even be included in each other. But for the specific question about AC^0, the answer is positive. On the one hand, NC^1 (and even L) is included in LinH by Nepomnjascij's theorem, and LinH-uniform AC^0 in your sense (which is commonly called FO-uniform) equals the usual uniform AC^0...  
> **username_1**: ... On the other hand, uniform AC^0 equals alternating logarithmic time with $O(1)$ alternations; the usual simulation of this machine model by constant-depth circuits makes nodes of the circuit be indexed by configurations of the logtime ATM, with edges corresponding to one configuration yielding another in one step. This can be checked not just in linear time, but even in coNLOGTIME (which is included in uniform AC^0). Thus, for any class $C$ between coNLOGTIME and LinH, $C$-uniform AC^0 in your sense equals the usual DLOGTIME-uniform AC^0. I'd expect the same to hold for any of the usual...  
> **username_1**: ... circuit classes that share the closure properties of AC^0, thus any potential counterexamples should be somewhat unnatural.  
> **username_0**: @EmilJeřábek then what about weaker e.g. DLOGTIME-uniform? NC0-uniform looks too hard it requires too complete linking  

---

## 0 answers

