CSDM - Lower Bounds for Circuits with $MOD_m$ Gates

Let $CC_{o(n)} \left[ m \right]$ 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_q$ in sub-linear size when $m, q \ge 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_q$. On the other hand, our results show circuits of type $MAJ \circ CC_{o(n)} \left[ m \right]$ need exponential size to compute $MOD_q$. 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 \circ CC_{o(n)} \left[ m \right] \circ AND_{ \in \log n,}$ where $\in > 0$ is a sufficiently small constant.

--$CC[m]$ circuits of constant depth need superlinear number of wires to compute both the AND and $MOD_q$ 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.