Algebraic methods in the theory of lower bounds for boolean circuit complexity

kbstr act 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 MOD, where p is a prime require Ezp(O(n’)) gates to calculate MOD, functions for any r # pm. This statement contains as special cases Yao’s PARITY result [ Ya 85] and Razborov’s new MAJORITY resul