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.