We consider several testing problems.
The first problem is testing graph isomorphism in the bounded-degree graph model. We focus on the case where one of the graphs is fixed. Our main result is that, for almost all d-regular n-vertex graphs H, testing isomorphism to H (the fixed graph) can be done using $\tildeO(\sqrt n)$ queries. This result is shown to be optimal (up to a polylog factor) by a matching lower bound, which also holds for almost all graphs H. We also consider the graph isomorphism problem in the specific case where the degree bound is two. This leads to a general tester for every graph property, in this special case. The query complexity of the tester is $\poly(1/\epsilon)$, which means it depends only on the proximity parameter epsilon.
In addition, we consider the topic of testing group properties. We focus on the problem of testing whether a binary operation over $S$ is a group operation. Our main result is a tester of running-time $\tildeO(|S|)$, which improves over the previously known tester that has running time $\tildeO(|S|^{3/2})$. This tester leads easily to a tester for abelian groups with the same running time. We also show a lower bound of $\Omega(log|S|)$ for testing each of the properties of being a group, an Abelian group, or a cyclic group.
Submitted to the Feinberg Graduate School of the Weizmann Institute of Science, Feb 2024.
Available: the thesis (in PDF file).
Back to Oded Goldreich's homepage.