|Previous slide||Next slide||Back to the first slide||View Graphic 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)