Polynomial Identity Testing and Algebraic Complexity

多项式恒等式检验(PIT)问题--确定给定算术电路的输出是否同为零--在算术电路复杂性理论中占有举足轻重的地位。PIT用于许多基本的复杂性结果，包括素性检验、PCP定理，以及许多其他问题可以归结为多项式恒等式的检验。求解PIT问题的有效随机化算法是已知的，而复杂性理论中的一个主要挑战是找到解决该问题的确定性算法。随机化复杂性类别的无条件去随机化预计将是非常困难的问题，因为它已知需要电路下限。尽管如此，著名的AKS素性检验等结果仍激发了人们的希望，即对于具有良好代数结构的特定问题，算法的去随机化可能是可能的。一个突出的候选问题是完美匹配问题(对于并行算法)，并将其推广到拟阵。该项目的目标是获得更一般结构的去随机化结果。与PIT相连，计算的算术模型的下限是重点，就像算术电路、分支程序或公式一样。这也激发了对相应复杂性类的闭包性质的研究。

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.