I am going through Computational Complexity by Arora and Barak, and there I came across the proof of why mod $p$ gates cannot be computed by $ACC^0[q]$ circuits, where $p$ and $q$ are distinct primes. The book proves it for $p=2$ and $q=3$, and I am facing difficulties generalizing this result for arbitrary $p$ and $q$.

The proof uses two lemmas. The first one states that any $ACC^0[3]$ circuit can be approximated via a low degree polynomial $\in F_3[x]$. The change in the first lemma to generalize it to arbitrary primes, $p$ and $q$, is straightforward.

But in the second lemma, where they changed $f\colon\{0,1\}^n\to\{0,1\}$ to $f\colon\{-1,1\}^n\to\{-1,1\}$ and defined a function $\prod_{i=1}^n y_i$ which represents parity, I do not quite get how to generalize to arbitrary $p$ and $q$.

  • $\begingroup$ Try replacing $\{-1,1\}$ with the set of $p$th roots of unity. $\endgroup$ Oct 3 '20 at 10:45
  • $\begingroup$ How to change $\{0,1\}$ to $\{1,\zeta_p\}$ without changing the criteria $deg(f)<n^{1/2}$ ? $\endgroup$ Oct 3 '20 at 14:17
  • $\begingroup$ I don't understand your question. The polynomial $\prod_{i=1}^n y_i$ has degree $n$. $\endgroup$ Oct 3 '20 at 14:17
  • $\begingroup$ I mean what transformation should I use? $\endgroup$ Oct 3 '20 at 14:21
  • $\begingroup$ How about $x \mapsto 1 + (\zeta_p-1)x$? It has degree 1, just like the special case $x \mapsto 1-2x$. $\endgroup$ Oct 3 '20 at 14:22

Your Answer

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

Browse other questions tagged or ask your own question.