| SHORT TALKS BY POSTDOCTORAL MEMBERS | |
| 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.