1
$\begingroup$

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, according to Barrington et. al's paper "On Uniformity Within $NC^1$" (1). However, this definition assumes that whether there is a wire or not between two gates is a binary choice. While this is true for $AND/OR$-based circuit classes like $AC^0$, other circuit classes like $CC^0$ and especially $TC^0$ assume that circuits can have an arbitrary constant or even $O(n)$ number of wires between two gates.

My questions are:

  • Is there a standard way in the literature to extend the definition of dlogtime-uniformity with wire weights greater than 1?
  • Is there a standard way to add this feature to logical characterizations of these families (e.g. $FO[bit]$)?
$\endgroup$
2
  • 1
    $\begingroup$ I’m not sure where your definition is taken from, but it is inappropriate already to plain bounded fan-in circuits with connectives that are not commutative or not associative, such as $\to$. I don’t think this is standard. For example, the original definition of a direct or extended connection language in Ruzzo’s “Uniform circuit complexity” includes an explicit specification which gate is the left input and which is the right input (and these two might be the same). It is obvious how to adjust it if you need more than 2 input wires, just label the input wires accordingly. $\endgroup$ – Emil Jeřábek Jan 20 at 7:50
  • 1
    $\begingroup$ Well then, do use Ruzzo’s definition. It will solve your problem. $\endgroup$ – Emil Jeřábek Jan 20 at 19:23
1
$\begingroup$

After re-reading Barrington et al., it seems that the case of $CC^0$ can be handled by using "group quantifiers", which allow for quantifiers to act over finite groups (i.e. $\mathbb{Z}/m\mathbb{Z}$) directly, while still using a binary representation under the hood so that the original definition of $DLOGTIME$-uniformity can still be used. With group quantifiers, wire weights (or any arbitrary constant-size function) can be simulated with a formula over the bits of the representation. I am still unsure how this might extend to a class like $TC^0$ that operates over an infinite monoid/group (or at least one that grows with $n$), but this answers the core of the question I had.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.