Polynomial Identity Testing and Algebraic Complexity

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

The problem of polynomial identity testing (PIT) -- deciding if the output of a given arithmetic circuit is identically zero -- occupies a pivotal position in the theory of arithmetic circuit complexity. PIT is used in many fundamental Complexity results including primality testing, the PCP-Theorem, and many other problems can be cast as checking polynomial identities. Efficient randomized algorithms for PIT are known and a major challenge in Complexity Theory is to find deterministic algorithms for this problem. Unconditional derandomization of randomized complexity classes are expected to be very hard problems because it is known to entail circuit lower bounds. Still results such as the famous AKS primality test inspire hope that derandomization of algorithms for specific problems with nice algebraic structure may be possible. A prominent candidate is the perfect matching problem (for parallel algorithms) and generalizations of it to matroids. The goal of the project is to obtain derandomization results for more general structures. Connected to PIT, lower bounds for arithmetic models of computation are in the focus, like for arithmetic circuits, branching programs, or formulas. This also motivates the study of closure properties of the respective complexity classes.