We study optimization versions of Graph Isomorphism. Given two graphs $G_1,G_2$, we are interested in finding a bijection $\pi$ from $V(G_1)$ to $V(G_2)$ that maximizes the number of matches (edges mapped to edges or non-edges mapped to non-edges). We give an $n^{O(\log n)}$ time approximation scheme that for any constant ... more >>>

Let $G=\langle S\rangle$ be a solvable permutation group given as input by generating set $S$. I.e.\ $G$ is a solvable subgroup of the symmetric group $S_n$. We give a deterministic polynomial-time algorithm that computes an expanding generator set for $G$. More precisely, given a constant $\lambda <1$ we can compute ... more >>>

Given two $n$-variable boolean functions $f$ and $g$, we study the problem of computing an $\varepsilon$-approximate isomorphism between them. I.e.\ a permutation $\pi$ of the $n$ variables such that $f(x_1,x_2,\ldots,x_n)$ and $g(x_{\pi(1)},x_{\pi(2)},\ldots,x_{\pi(n)})$ differ on at most an $\varepsilon$ fraction of all boolean inputs $\{0,1\}^n$. We give a randomized $2^{O(\sqrt{n}\log(n)^{O(1)})}$ algorithm ... more >>>