Group-Theoretic Computation: Complexity and Applications

这项研究涉及群体的基本计算问题。一个中心主题涉及图同构测试和相关问题。多项式时间结果以及其他复杂性理论问题正在扩展到矩阵群，这是数学科学应用的共同领域。在理论的基础上进行了实践和实验，并有效地实现了置换群方法和新的矩阵群方法，从而保持了保证的渐近时序。同样的群论问题与约束满足问题的新方法有关，该方法利用对称性并可以增强现有的应用系统。

The research deals with basic computational problems for groups. A central theme involves graph-isomorphism testing and related issues. Polynomial-time results as well as other complexity theoretic issues are being extended to matrix groups, the common domain for applications in the mathematical sciences. Implementation and experimentation is accompanying the theory, and both the permutation-group and new matrix-group methods are being efficiently implemented so that the guaranteed asymptotic timings are retained. The same group-theoretic problems are relevant to a new approach to constraint-satisfaction problems that exploits symmetries and can augment existing applied systems.