Key points are not available for this paper at this time.
We use algebraic methods to get lower bounds for complexity of different functions based on constant depth unbounded fan-in circuits with the given set of basic operations. In particular, we prove that depth k circuits with gates NOT, OR and MODp where p is a prime require Exp(Ο(n1/2k)) gates to calculate MODr functions for any r ≠ pm. This statement contains as special cases Yao's PARITY result Ya 85 and Razborov's new MAJORITY result Ra 86 (MODm gate is an oracle which outputs zero, if the number of ones is divisible by m).
Roman Smolensky (Thu,) studied this question.