Computer Science/Discrete Mathematics Seminar II

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. This lecture is likely to continue the following Tuesday, Sep 23.