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.