Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

# Questions tagged [uniformity]

The tag has no usage guidance.

15 questions
Filter by
Sorted by
Tagged with
142 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 ...
• 580
115 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.5k
1 vote
68 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, ...
• 580
120 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 ...
• 580
1 vote
114 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$...
• 580
185 views

• 12.5k
305 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,022
310 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
372 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,022
368 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
205 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