Personal tools
You are here: Home Events Algorithms & Complexity Group Meetings Algorithms and Complexity Meeting: Maurice Jansen

Algorithms and Complexity Meeting: Maurice Jansen

What
  • Algorithms and Complexity Meeting
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 well-known Schwartz-Zippel 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.

Document Actions