Derandomizing Polynomial Identity Testing and the Isolation Lemma

点击翻译按钮获取中文摘要

A number of important computational problems are algebraic in nature. Algorithmic questions about these problems motivate research in Computational Complexity. In the past, efforts to understand these problems have led to some of the most important developments in Complexity Theory. These problems also lie at the heart of several significant open problems of current interest. Some prominent examples include primality testing, perfect matching, or various equivalence problems for certain circuits and branching programs. The common property of many of these problems is that they can be transformed into polynomial identities. Randomized algorithm check such identities by evaluating these polynomials at random points [Sch80, Zip79]. This led to the definition of randomized complexity classes like BPP and RP and provided one of the earliest examples of the power of randomness in computation. The celebrated deterministic polynomial-time algorithm of Agrawal, Kayal and Saxena [AKS04] can be viewed as part of a general program of derandomization, one of the most active research areas within Computational Complexity. Although unconditional derandomization of randomized complexity classes is now known to entail circuit lower bounds [IW97, KI04], the AKS result inspires hope that derandomization of algorithms for specific problems with nice algebraic structure may be possible. This is the goal of the project.