The following paper briefly mentions the power of $MOD_6$ gates (page 3), and relies on the unstated fact that every boolean function can be computed with an arithmetic circuit of depth 2 over $\mathbb{F}_3$. I'm not sure how this is done.
$\begingroup$
$\endgroup$
4
-
5$\begingroup$ Asking about a claimed fact in a research paper is definitely grad-student level, which I think is fine for this site. $\endgroup$– Suresh VenkatMay 6, 2012 at 17:44
-
3$\begingroup$ @Suresh: That is a very broad statement. $\endgroup$– Tsuyoshi ItoMay 6, 2012 at 19:21
-
$\begingroup$ @TsuyoshiIto: Somehow I knew you'd object to it :) $\endgroup$– Suresh VenkatMay 6, 2012 at 20:23
-
2$\begingroup$ @Suresh: Honestly, I do not know why you posted that obviously incorrect claim. In addition, I do not know what those four users who voted your comment up are thinking. If you wanted to provoke me for some reason, you won. $\endgroup$– Tsuyoshi ItoMay 6, 2012 at 21:59
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Every function $\mathbb{F}_p^n \longrightarrow \mathbb{F}_p$ (where $p$ is prime) can be written as a polynomial. For the proof, consider all $p^n$ monomials, and show that they are linearly independent.