<p>After re-reading Barrington et al., it seems that the case of <span class="math-container">$CC^0$</span> can be handled by using &quot;group quantifiers&quot;, which allow for quantifiers to act over finite groups (i.e. <span class="math-container">$\mathbb{Z}/m\mathbb{Z}$</span>) directly, while still using a binary representation under the hood so that the original definition of <span class="math-container">$DLOGTIME$</span>-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 <span class="math-container">$TC^0$</span> that operates over an infinite monoid/group (or at least one that grows with <span class="math-container">$n$</span>), but this answers the core of the question I had.</p>

CC BY-SA 4.0
2021-01-20T22:38:40.607Z
2021-01-20T22:38:40.607Z
Jake
<p>The definition of a <span class="math-container">$DLOGTIME$</span>-uniform circuit family is based on a Turing machine that accepts the language <span class="math-container">$\langle t, a, b \rangle$</span>, where gate <span class="math-container">$a$</span> is of type <span class="math-container">$t$</span> and has gate <span class="math-container">$b$</span> as a child, according to Barrington et. al's paper &quot;On Uniformity Within <span class="math-container">$NC^1$</span>&quot; (<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.75.5866&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">1</a>). However, this definition assumes that whether there is a wire or not between two gates is a binary choice. While this is true for <span class="math-container">$AND/OR$</span>-based circuit classes like <span class="math-container">$AC^0$</span>, other circuit classes like <span class="math-container">$CC^0$</span> and especially <span class="math-container">$TC^0$</span> assume that circuits can have an arbitrary constant or even <span class="math-container">$O(n)$</span> number of wires between two gates.</p>
<p>My questions are:</p>
<ul>
<li>Is there a standard way in the literature to extend the definition of dlogtime-uniformity with wire weights greater than 1?</li>
<li>Is there a standard way to add this feature to logical characterizations of these families (e.g. <span class="math-container">$FO[bit]$</span>)?</li>
</ul>

CC BY-SA 4.0
2021-01-20T07:50:48.350Z
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.
Emil Jeřábek
CC BY-SA 4.0
2021-01-20T19:23:47.737Z
Well then, *do* use Ruzzo’s definition. It will solve your problem.
Emil Jeřábek
<lo.logic><circuit-complexity><uniformity><bounded-depth>
Variable wire weights in DLOGTIME-uniform circuits
Jake
# Variable wire weights in DLOGTIME-uniform circuits

(Asked by: username_0 on 2021-01-20)

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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.75.5866&rep=rep1&type=pdf)). 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]$)?

**Tags:** lo.logic, circuit-complexity, uniformity, bounded-depth

> **Comments:**
> **username_1**: 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.  
> **username_1**: Well then, *do* use Ruzzo’s definition. It will solve your problem.  

---

## 1 answers

### Answer by username_0 on 2021-01-20. Score: 1 | Accepted answer

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.


---

