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".