# Questions tagged [uniformity]

The tag has no usage guidance.

18 questions
Filter by
Sorted by
Tagged with
40 views

### Do uniformity lower than DLOGTIME rlead to same result?

Maybe an answer to this Here input of length and position is binary rather than unary, so traditional "DLOGTIME-uniform" is now "O(n)-uniform". (If traditional "DLOGTIME-...
• 111
26 views

### What are the two quantities involved in the tradeoff for a language to follow Zipf's law?

In any human (and non-human) language the frequency distribution of words follows Zipf's law, which states that the slope of the linear regression for the frequency distribution of words vs the rank ...
• 101
91 views

• 12.6k
1 vote
83 views

### Variable wire weights in DLOGTIME-uniform circuits

The definition of a $DLOGTIME$-uniform circuit family is based on a Turing machine that accepts the language $\langle t, a, b \rangle$, where gate $a$ is of type $t$ and has gate $b$ as a child, ...
• 945
129 views

### Proof of $DLOGTIME-CC^0 = MOD[<,bit]$

Let $CC^0[m]$ be the class of constant-depth, polynomial-sized circuits consisting entirely of $MOD_m$ gates, which put out $1$ iff the sum of their inputs $\equiv 0~(\textrm{mod}~m)$. In the same way ...
• 945
1 vote
116 views

### $\mathit{FO}[+,\times]$ seems more powerful than $\mathit{DLOGTIME}$-uniform $\mathit{AC}^0$?

I’ve been reading up on the connection between first order logic and small circuit complexity classes, and specifically Barrington, Immerman, and Straubing’s paper “On Uniformity Within $\mathit{NC}^1$...
• 945
194 views

• 12.6k
319 views

### Do we have any nontrivial uniform circuits?

Given an algorithm running in time $t(n)$, we can convert it into a "trivial" uniform circuit family for the same problem of size at most $\approx t(n)\log t(n)$. On the other hand, it might ...
• 7,140
317 views

### Size hierachy for uniform circuits

There is the size hierarchy theorem for non-uniform circuits. Do we have any size hierarchy theorem for any kind of uniform circuits ? (By uniform here, I mean DLOGTIME uniform. But I don't know ...
• 1,120
374 views

### The Examiner's Problem (uniform generation of SAT decision instances/answers)

A course's teaching assistant has managed to write a program that (deterministically) generates difficult exam questions. Now, she'd like to write a program that generates the corresponding answers. ...
• 7,140
373 views

### Proof Complexity and Circuit Lower bound for coNP

I have two questions (1)Circuit lower bound for coNP TAUT is a set of formulae such that any formula in TAUT is satisfied for all boolean assignments. UnSAT is the complement problem of SAT. It is ...
• 317
206 views

### Other types of uniformity for circuits (incl. by small modifications)

I've seen poly-time and logspace uniformity for circuit families, typically defined as the existence of a poly-time/logspace Turing machine "generator" that outputs the correctly sized circuit $C_n$ ...
• 255