Short Talks by Postdoctoral Members

In this talk I will consider depth-three circuits having a MAJORITY gate at the output, MODULO(m) gates in the middle, and polylog-degree AND gates at the inputs. It is conjectured that such circuits need exponential size to compute the MODULO(q) function, if gcd(m,q)=1. I will explain briefly the significance of such circuits to complexity theory and the connection between obtaining lower bounds for them and bounding the absolute value of certain exponential sums on {0,1} inputs for polylog-degree multivariate polynomials modulo q.