Multiple Product Modulo Arbitrary Numbers

Letnbinary numbers of lengthnbe given. The Boolean function “Multiple Product”MPn asks for (some binary representation of ) the value of their product. It has been shown (K. -Y. Siu and V. Roychowdhury, On optimal depth threshold circuits for multiplication and related problems, SIAM J. Discrete Math. 7, 285–292 (1994)) that this function can be computed in polynomial-size threshold circuits of depth 4. For many other arithmetic functions, circuits of depth 3 are known. They are mostly based on the fact that the value of the considered function modulo some prime numbers p can be computed easily in threshold circuits of depth 2. In this paper, we investigate the complexity of computingMPn modulomby depth-2 threshold circuits. It turns out that for all but a few integersm, exponential size is required. In particular, it is shown that form∈{2, 4, 8}, polynomial-size circuits exist, form∈{3, 6, 12, 24}, the question remains open and in all other cases, exponential-size circuits are required. The result still holds if we allowmto grow withn.

Authors

• Claudia Bertram-Kretzberg
• Thomas Hofmeister

Keywords

No keywords are indexed for this paper.