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.