ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > AUTHORS > LASZLO BABAI:
All reports by Author Laszlo Babai:

TR08-040 | 3rd April 2008
Sourav Chakraborty, Laszlo Babai

Property Testing of Equivalence under a Permutation Group Action

For a permutation group $G$ acting on the set $\Omega$ we say that two strings $x,y\,:\,\Omega\to\boole$ are {\em $G$-isomorphic} if they are equivalent under the action of $G$, \ie, if for some $\pi\in G$ we have $x(i^{\pi})=y(i)$ for all $i\in\Omega$. Cyclic Shift, Graph Isomorphism and Hypergraph Isomorphism are special cases, ... more >>>



ISSN 1433-8092 | Imprint