Computer Science/Discrete Mathematics Seminar II

A celebrated theorem of Razborov/Smolensky says that constant depth circuits comprising AND/OR/MOD_{p^k} gates of unbounded fan-in, require exponential size to compute the MAJORITY function if p is a fixed prime and k is a fixed integer. Extending this result to the case when p is a number having more than one distinct prime factor (like 6) remains a major open problem. In particular, it remains consistent with our knowledge that every problem in NP has linear size depth-three circuits comprising only MOD_6 gates. We go through some approaches for making progress on this problem. In the process, a diverse set of techniques are introduced that are interesting in their own right.