All reports by Author Yadu Vasudev:

__
TR12-078
| 14th June 2012
__

Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Yadu Vasudev#### Approximate Graph Isomorphism

__
TR11-140
| 31st October 2011
__

Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar, Yadu Vasudev#### Expanding Generator Sets for Solvable Permutation Groups

Revisions: 1

__
TR11-137
| 14th October 2011
__

Vikraman Arvind, Yadu Vasudev#### Isomorphism Testing of Boolean Functions Computable by Constant Depth Circuits

Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Yadu Vasudev

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

Vikraman Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar, Yadu Vasudev

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

Vikraman Arvind, Yadu Vasudev

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