| COMPUTER SCIENCE/DISCRETE MATH II | |
| Topic: | Lower Bounds for Circuits with MOD_m Gates |
| Speaker: | Arkadev Chattopadhyay |
| Affiliation: | Member, School of Mathematics |
| Date: | Tuesday, October 14 |
| Time/Room: | 10:30am - 12:30pm/S-101 |
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.