<p>I have reached out to the authors of papers [1] and [2], and it seems that the claims were both in error, leaving this an open question.</p>

CC BY-SA 4.0
2021-09-29T19:08:35.993Z
2021-09-29T19:08:35.993Z
Jake
<p>Let <span class="math-container">$CC^0[m]$</span> be the class of constant-depth, polynomial-sized circuits consisting entirely of <span class="math-container">$MOD_m$</span> gates, which put out <span class="math-container">$1$</span> iff the sum of their inputs <span class="math-container">$\equiv 0~(\textrm{mod}~m)$</span>. In the same way that <span class="math-container">$DLOGTIME$</span>-uniform <span class="math-container">$AC^0$</span> is equivalent to <span class="math-container">$FO[&lt;,bit] = FO[+,*]$</span>, in multiple sources <a href="https://arxiv.org/abs/cs/0701154" rel="noreferrer">1</a>, <a href="https://arxiv.org/abs/1204.6179" rel="noreferrer">2</a> it's asserted that <span class="math-container">$DLOGTIME$</span>-uniform <span class="math-container">$CC^0$</span> is equivalent to <span class="math-container">$MOD[+,*]$</span>, the set of logical sentences using only the modular quantifier <span class="math-container">$\exists^{(m,k)}$</span> that evaluates to true iff the number of satisfying solutions is congruent to <span class="math-container">$k$</span> mod <span class="math-container">$m$</span>.</p>
<p>However, all of the sources that are cited for these claims <a href="https://people.cs.umass.edu/%7Eimmerman/pub/bis.pdf" rel="noreferrer">3</a>, [4], [5] only provide proofs for the classes <span class="math-container">$AC^0, ACC^0, TC^0, NC^1$</span> and rely on the usage of standard quantifiers <span class="math-container">$\forall, \exists$</span>, which are not proven to be expressible in <span class="math-container">$CC^0$</span>. Does anyone know of how to modify the original proofs of <span class="math-container">$DLOGTIME-AC^0 = FO[&lt;,bit] = FO[+,*]$</span> to achieve <span class="math-container">$DLOGTIME-CC^0 = MOD[&lt;,bit] = MOD[+,*]$</span> without using these quantifiers, or a source for such proofs?</p>
<p>[4]: Introduction to Circuit Complexity: A Uniform Approach by Heribert Vollmer</p>
<p>[5]: Descriptive Complexity by Neil Immerman</p>
<p>(These proofs mostly just follow the one laid out in <a href="https://people.cs.umass.edu/%7Eimmerman/pub/bis.pdf" rel="noreferrer">3</a>)</p>

<lo.logic><circuit-complexity><uniformity>
Proof of $DLOGTIME-CC^0 = MOD[<,bit]$
Jake
# Proof of $DLOGTIME-CC^0 = MOD[<,bit]$

(Asked by: username_0 on 2020-10-28)

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 that $DLOGTIME$-uniform $AC^0$ is equivalent to $FO[<,bit] = FO[+,\*]$, in multiple sources [1](https://arxiv.org/abs/cs/0701154), [2](https://arxiv.org/abs/1204.6179) it's asserted that $DLOGTIME$-uniform $CC^0$ is equivalent to $MOD[+,\*]$, the set of logical sentences using only the modular quantifier $\exists^{(m,k)}$ that evaluates to true iff the number of satisfying solutions is congruent to $k$ mod $m$.

However, all of the sources that are cited for these claims [3](https://people.cs.umass.edu/%7Eimmerman/pub/bis.pdf), [4], [5] only provide proofs for the classes $AC^0, ACC^0, TC^0, NC^1$ and rely on the usage of standard quantifiers $\forall, \exists$, which are not proven to be expressible in $CC^0$. Does anyone know of how to modify the original proofs of $DLOGTIME-AC^0 = FO[<,bit] = FO[+,\*]$ to achieve $DLOGTIME-CC^0 = MOD[<,bit] = MOD[+,\*]$ without using these quantifiers, or a source for such proofs?

[4]: Introduction to Circuit Complexity: A Uniform Approach by Heribert Vollmer

[5]: Descriptive Complexity by Neil Immerman

(These proofs mostly just follow the one laid out in [3](https://people.cs.umass.edu/%7Eimmerman/pub/bis.pdf))

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

---

## 1 answers

### Answer by username_0 on 2021-09-29. Score: 5 | Accepted answer

I have reached out to the authors of papers [1] and [2], and it seems that the claims were both in error, leaving this an open question.


---

