A study on approximation of isomorphism problems

判定给定的两个对象(如图形和函数)是否“本质”相同的问题称为同构问题。同构问题已经得到了广泛的研究，但它们是否在多项式时间内是可处理的仍是个未知数。在这个项目中，我考虑了同构问题的一种变体，在这种问题中，我们计算两个对象的距离，而不是它们是否相同。在被称为“属性测试”和“近似算法”的范式下，我获得了关于这个变体的几个新结果。

The problems of deciding whether given two objects, such as graphs and functions, are "essentially" the same or not is called the isomorphism problems. The isomorphism problems have been studied intensively, but whether they are tractable in polynomial time remains open. In this project, I considered a variant of the isomorphism problems in which we compute how close two objects are instead of whether they are the same or not. I obtained several new results about this variant under the paradigms called "property testing" and "approximation algorithms".