Circuit Lower Bounds and Incomplete Exponential Sums

Topic:Circuit Lower Bounds and Incomplete Exponential Sums
Speaker:Vladimir Trifonov
Affiliation:University of Texas at Austin and Member, School of Mathematics
Date:Wednesday, October 4
Time/Room:3:15pm - 4:15pm/S-101

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.