Algorithms and Complexity Meeting: Maurice Jansen
What 


When 
Nov 17, 2010 from 03:00 PM to 04:00 PM 
Where  5.02 
Add event to calendar 
vCal iCal 
For the PIT problem one is given a multivariate polynomial $f$ in some succinct representation, and the question is to decide whether $f$ equals the zero polynomial or not. For example, the succinct representation could be a matrix $M$ of variables and field constants, with $f$ equaling the (symbolic) determinant of $M$. Using randomization this problem is efficiently solvable using the wellknown SchwartzZippel test. We will look at the major open problem of derandomization of PIT, and how it relates to lower bounds. I will give a *short* introduction into the area of polynomial identity testing (PIT), followed by an overview of some of the work I have done on the problem.
One succinct representation for which PIT will be considered extensively in this talk, is the algebraic branching program (ABP). The latter model provides a characterization of the determinant polynomial. I will show some unconditional derandomization results for (suitably restricted) ABPs. I will also revisit ideas by Kabanets and Impagliazzo for leveraging arithmetic hardness assumptions to derandomize arithmetic circuits PIT. Next I will touch upon some recent result that is aimed at refining this general scheme to the ABP model.