Lower Bounds for Circuits with MOD_m Gates

Video of this lecture

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 7
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.