I. INTRODUCTION
A fundamental open problem in theoretical computer science is to understand the computational power of counting modulo composite numbers. For example, we do not know if hard problems like SATISFIA-BILITY have efficient depth-three circuits comprising only gates. This is in contrast to the classical theorem of Razborov [1] and Smolensky [2] that says constant-depth circuits having only AND, OR and gates cannot compute even the function in sub-exponential size, i.e. in size , when are co-prime and when has only one prime factor. Smolensky [2] conjectured that this theorem extends to all , but despite a series of attempts over two decades, this conjecture remains wide open. While Smolensky's conjecture easily implies that not all functions computable in deterministic linear time have efficient circuits, the best one can prove is the recent breakthrough result of Williams [3] who showed that non-deterministic exponential time does not have efficient circuits.