Randomized Complexity Classes and Complexity in Finite Groups

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

This project continues the investigator's research, with two distinct parts. The first part is to explore the scope of the new low degree polynomial techniques in simulation of complexity classes. These methods were invented very recently, with striking results: characterizations of the power of interactive proofs and multiprover interactive proofs. The new methods do not relativize, a fact with potentially far reaching consequences in structural complexity theory. The second part is to further develop the algorithmic machinery that put basic permutation group manipulation in NC and yielded an order of magnitude improvement in sequential worst case asymptotic time complexity. A striking feature of the new methods is the depth of group theory required for their analysis. Indeed, even for rudimentary tasks such as membership testing in permutation groups, a number of consequences of the classification of finite simple groups have to be invoked.