Previous slide Next slide Back to the first slide View text version


- Razborov-Smolensky - For distinct primes p and q, Mod_p can not be computed in bounded depth with Mod_q gates

- Linial-Mansour-Nisan Fourier Transform Methods to approximate circuits by low-degree polynomials over rationals and reals. Applications to circuit complexity and learning theory.

- Open even for Mod_q for non-prime q (such as q=6)