COMPUTER SCIENCE/DISCRETE MATH II | |

Topic: | Multilinear Computation |

Speaker: | Amir Yehudayoff |

Affiliation: | Member, School of Mathematics |

Date: | Tuesday, September 23 |

Time/Room: | 10:30am - 12:30pm/S-101 |

Nisan and Wigderson defined the model of multilinear circuits as a natural model for computing multilinear polynomials (such as matrix product and the Permanent). We will go over several results regarding such circuits -- a few structural results, and the lower bounds that `followed' them. We will start by discussing the different ways to define a multilinear computation, and we will sketch the multilinear world as we know it. We will then go over two results of Raz: a super-polynomial lower bound for multilinear formulas computing the Determinant and the Permanent, and a separation between multilinear circuits and formulas size. We will go over the roughly n^{4/3} lower bound for multilinear circuits (this was a joint work with Shpilka and Raz). We will also discuss constant depth multilinear circuits: exponential lower bounds and separations (joint work with Raz). If time permits, we will discuss several restrictions of multilinear circuits, and their connection to extractors and communication complexity.