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.

Filter by
Sorted by
Tagged with
3 votes
1 answer
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 ...
user avatar
  • 580
0 votes
0 answers
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\...
user avatar
  • 12.5k
1 vote
1 answer
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, ...
user avatar
  • 580
9 votes
1 answer
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 ...
user avatar
  • 580
1 vote
0 answers
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$...
user avatar
  • 580
4 votes
1 answer
185 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 $\...
user avatar
  • 21.3k
2 votes
0 answers
200 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 ...
user avatar
  • 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 $\...
user avatar
  • 12.5k
13 votes
1 answer
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 ...
user avatar
  • 7,022
7 votes
2 answers
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 ...
user avatar
  • 1,120
11 votes
2 answers
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. ...
user avatar
  • 7,022
0 votes
1 answer
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 ...
user avatar
  • 317
5 votes
1 answer
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$ ...
user avatar
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/...
user avatar
  • 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(...
user avatar
  • 21.3k