Lower bounds for circuits with MOD_m gates

Abstract

Let CC <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">o(n)</sub> [m] be the class of circuits that have size o(n) and in which all gates are MOD[m] gates. We show that CC [m] circuits cannot compute MOD <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</sub> in sub-linear size when m, q > 1 are co-prime integers. No non-trivial lower bounds were known before on the size of CC [m] circuits of constant depth for computing MOD <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</sub> . On the other hand, our results show circuits of type MAJ o CC <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">o(n)</sub> [m] need exponential size to compute MOD <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q </sub> . Using Bourgain's recent breakthrough result on estimates of exponential sums, we extend our bound to the case where small fan-in AND gates are allowed at the bottom of such circuits i.e. circuits of type MAJ o CC[m] o AND <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">epsiv log n</sub> , where epsiv > 0 is a sufficiently small constant. CC [m] circuits of constant depth need superlinear number of wires to compute both the AND and MOD <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</sub> functions. To prove this, we show that any circuit computing such functions has a certain connectivity property that is similar to that of superconcentration. We show a superlinear lower bound on the number of edges of such graphs extending results on superconcentrators