<p>Although not exactly what you're looking for, <a href="https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2019.23" rel="nofollow noreferrer">this paper</a> seems to be the most current (2019) efforts towards tight <span class="math-container">$AC^0[2]$</span> bounds as of yet, and provides a good summary of the difference between <span class="math-container">$AC^0$</span> and <span class="math-container">$AC^0[2]$</span> bounds.</p>

CC BY-SA 4.0
2021-02-22T03:49:52.900Z
2021-02-22T03:49:52.900Z
Jake
<p>It is known <span class="math-container">$AC^0[2]$</span> cannot get majority function.</p>
<p>Is there a literature on simulation of <span class="math-container">$MAJ$</span> function utilizing <span class="math-container">$AC^0[2,3,\dots,p]$</span> gates for a finite fixed set of primes <span class="math-container">$2$</span> to <span class="math-container">$p=O(1)$</span>?</p>
<p>What is the best we found?</p>

<cc.complexity-theory><complexity-classes><lower-bounds><big-picture><ac0>
What is the best simulation of majority utilizing $\bmod\{2,3,\dots,p\}$ gates?
Turbo
# What is the best simulation of majority utilizing $\bmod\{2,3,\dots,p\}$ gates?

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

It is known $AC^0[2]$ cannot get majority function.

Is there a literature on simulation of $MAJ$ function utilizing $AC^0[2,3,\dots,p]$ gates for a finite fixed set of primes $2$ to $p=O(1)$?

What is the best we found?

**Tags:** cc.complexity-theory, complexity-classes, lower-bounds, big-picture, ac0


---

## 1 answers

### Answer by username_1 on 2021-02-22. Score: 1

Although not exactly what you're looking for, [this paper](https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2019.23) seems to be the most current (2019) efforts towards tight $AC^0[2]$ bounds as of yet, and provides a good summary of the difference between $AC^0$ and $AC^0[2]$ bounds.


---

