Group:Student Seminar
Title: The Seminal Result by Ran Raz
Speaker: Youming Qiao University
Time: 2010-11-04 15:30-2010-11-04 17:00
Venue: FIT 1-222

Abstract:

In arithmetic circuit complexity, a circuit is (semantically) multilinear if every gate computes a multilinear polynomial. Being a natural circuit class, it has been drawing people's attention for some time. In 2004, Ran Raz proved super-polynomial lower bound for multilinear formula to compute determinant and permanent. The proof is a clever combination of partial derivative sets developed by Nisan and Widgerson and random restriction used to show lower bound of boolean functions. In the talk we will try to cover the main idea of the proof.




Short Bio: