Questions tagged [uniformity]
The uniformity tag has no usage guidance.
18
questions
0
votes
0
answers
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
0
votes
0
answers
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
0
votes
0
answers
91
views
Non-uniformity assumptions in circuit complexity
I recently came accross the following standard inclusion of complexity classes:
$$\textbf{NC}^0 \subseteq \textbf{AC}^0 \subseteq \textbf{NC}^1 \subseteq \textbf{L} \subseteq \textbf{NL} \subseteq \...
- 547
3
votes
1
answer
161
views
Circuit uniformities more restrictive than $DLOGTIME$
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 ...
- 945
0
votes
0
answers
118
views
$\mathsf{ACC}^0$ and $\mathsf{TC}^0$ with $\mathsf{Cuniform}$-$\oplus\mathsf{L}$ or $\mathsf{Cuniform}$-$\mathsf{NC}^1$ oracle?
$\mathsf{TC}^0$ is a small class with $\oplus\mathsf{L}$ containing it.
Following inclusions are known:
$$\mathsf{Cuniform}\mbox{ -}\mathsf{ACC}^0\subseteq\mathsf{Cuniform}\mbox{ -}\mathsf{TC}^0\...
- 12.6k
1
vote
1
answer
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
9
votes
1
answer
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
0
answers
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
4
votes
1
answer
194
views
Is length uniform AC0 computable?
Consider the following problem:
Input: A binary string $w$.
Output: $|w|$ as a binary number.
Is it possible to compute this
in $\mathsf{DLogTime}$-uniform $\mathsf{AC}^0$
(or equivalently in $\...
- 21.3k
2
votes
0
answers
204
views
Circuit complexity lower bounds and uniformity
I have troubles to understand how lower bounds w.r.t. circuit complexity and upper bounds w.r.t. uniform machine models can be used to show completeness results.
For example, the word problem for ...
- 31
1
vote
0
answers
166
views
Interlaced uniform versus non-uniform hierarchy
Denote $\mathsf{uniform}$ class with prefix $\mathsf{u}$ and $\mathsf{non}$-$\mathsf{uniform}$ class with prefix $\mathsf{nu}$.
In following some non-trivial standard notion of uniformity (like $\...
- 12.6k
13
votes
1
answer
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
7
votes
2
answers
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
11
votes
2
answers
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
0
votes
1
answer
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
5
votes
1
answer
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
34
votes
3
answers
2k
views
Is $AC^0/poly \cap NP$ contained in $P$?
I thought I would share this question as it might be interesting for other users here.
Assume that a function which is in a uniform class (like $NP$) is also in a small nonuniform class (like $AC^0/...
- 21.3k
28
votes
3
answers
2k
views
Is there a candidate for a natural problem in $P/poly - P$?
I want to know if non-uniformity helps computing functions in practice. It is easy to show that there are functions in $P/poly - P$, take any uncomputable function $f$ and consider the language {$0^{f(...
- 21.3k